acceptodds
Under review as a conference paper at ICLR 2027

Does Certified Robustness Generalize? A Neural Network Verification Study of Distribution Shift

Abstract

Certified robust accuracy (CRA) is the standard metric for quantifying worst-case adversarial robustness and for benchmarking certified defenses. However, CRA is by construction reported only on the in-distribution (ID) test set on which the model was trained. A largely understudied question is what CRA tells us about broader model behavior, in particular predictive accuracy, and whether the relationship between certified robustness and accuracy carries a transferable structure under distribution shift. This is non-trivial because formal verification is strictly stronger than any single-attack evaluation: a CRA guarantee asserts the absence of any adversarial example in an ℓ∞-ball, so the “on-the-line” transfer observed for clean accuracy and empirical attacks need not carry over. We present, to the best of our knowledge, the first systematic study of CRA under distribution shift for verification-tractable architectures, covering MNIST-FC, GTSRB-CNN, and CIFAR-CNN across structural and corruption shifts. Using clean-accuracy-matched model families and shared-property verification, we find that (i) the inter-model CRA ordering shows strong but imperfect agreement from ID to OOD, with statistically significant ID advantages retained under the tested shifts, and (ii) ID CRA correlates with OOD accuracy, calibration, and OOD detection across a multi-architecture ablation, acting as a model-selection proxy for several practical OOD properties. We further support these findings with a machine-checked theoretical framework that characterizes when ID CRA bounds OOD performance and with controlled-shift experiments that test the bound directly. Selecting by ID CRA incurs 0–7 percentage points of OOD CRA loss in the tested settings. These findings extend CRA’s value beyond robustness benchmarking, supporting its use as a model-selection signal for accuracy, calibration, and detection performance under distribution shift. Our code is available at [https://anonymous.4open.science/r/veri-generalization-anonymous](https://anonymous.4open.science/r/veri-generalization-anonymous).

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
certified robustness, neural network verification, distribution shift, certified robust accuracy

Reviews

Among:
Shape:
1234this paper, Bottom 9%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.50 over 4 reviews, above 9% of the others.
Reviewer_HjPyOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Paper addresses an interesting problem of generalisation of Certified Robust Accuracy (CRA) under distribution shift. The hypothesis under investigation is role of CRA for broader model behaviour like accuracy and if CRA and accuracy relationship is transferable under distribution shift. It shows that the CRA shows agreement from in-distribution (ID) to out-of-distribution (OOD) and interestingly, ID CRA correlates with OOD accuracy on various architectures and datasets.

Critical strengths

Paper addresses an interesting problem.

Critical weaknesses

Paper is generally well written but bit hard to follow due to long sentences. E.g., first contribution sentence is almost a paragraph. Whereas, conclusions statements are extremely summarised, Acronyms are introduced but never explained — authors assume that reader has specialised context already. An example is VNNLIB property set, beta-CROWN, etc). Limitations section reads disconnected from the paper, e.g., it talks about ReLU networks, but this is only introduced at Page 9. Conclusion has no link to the contribution as well the title of the paper. Section 5.3 conclusion, you say IC CRA is informative …accuracy, but it should be …. — this is confusing, either you conclude but it should NOT be, or write, so it should be.

Questions for authors

May main concern of the paper is (in my opinion), its flimsy nature. Asking generalisation of certified robustness is definitely a valid and important question, but it boils down to how you define the drift and OOD. You can change the definition of labels (cats are no more cats but dogs, or definition of cats can change without involving labels). You intuition is that in case of P(x,y) drift, CRA should not generalise, but in case of P(x), it should. My suggestion for improvement is that authors should do an explicit study of various forms of distribution shift, and be clear about conclusion they are reaching, rather then tangling them in mathematical subtleties.

Can you explain findings of Table 2 for me. Results suggest degradation (significant) of CRA for structural OOD and Corruption OOD. How does it back your main result? How does it answer your question of does certified robustness generalises?

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

The paper consider classifiers that can be certified to be robust under adversarial attacks, and wonder whether their accuracy and robustness property transfers when there is a distribution shift. A theoretical framework is provided, together with experiment findings.

Critical strengths

The paper has both theoretical study and empirical evaluations.

Critical weaknesses

Significance

My major concern is the significance of the paper, especially regarding its premise of transfering accuracy and robustness outside training distribution.

Let us say we have a certifiably robust classifier, which is robust on a certain region XX inside the domain RdR^d. Apriori, the classifier can have arbitrary behavior once you move outside XX, unless some simplicity assumption is made about the function class (e.g., in the extreme case, if the classifier is a constant / linear function). Why do we expect accuracy and robustness to transfer?

It appears that the paper focuses on the case that if the distribution shift is small, in the sense that the samples from the new distribution are inside the certified ball of samples from the training distribution. First, such an theoretical argument seems trivial. Second, this setting seems rather limited, since simple edits such as changing the background color of the images would move the image outside the certified ball.

Clarity

The paper could benefit from better presentation.

  1. The abstract is somewhat convoluted
    1. Line 20: "on-the-line" transfer is mentioned, but it is unclear what it is.
    2. Line 23: "verification-tractable architectures" what do you mean by verification tractable?
    3. "However, CRA is by construction reported only on the in-distribution (ID) test set on which the model was trained" -- the model is not trained on a test set.
  2. The AI statement claims "The research questions, study design, theoretical results, interpretation of findings and conclusions are the authors’ own". Please double check if this is a correct statement, since section 6 reads to the reviewer generated and hard to decipher.
Questions for authors

N/A

Reviewer_7L3AOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper asks whether in-distribution (ID) certified robust accuracy (CRA) transfers to out-of-distribution (OOD) data. It has three parts.

  • Theory. The certified ℓ∞ radius is 1-Lipschitz in the input (Prop. 1, triangle inequality). From this, Lemma 2 bounds the OOD CRA by the ID CRA at a larger radius minus a “shift defect” η̂(δ), the fraction of coupled pairs that move more than δ. Theorem 1 gives a sufficient condition for a pairwise CRA ranking to survive a shift. Theorem 2 bounds OOD loss by 1 − CRA(ID, δ) + η̂(δ). All results are checked in Lean 4.
  • Natural-shift experiments. Three clean-accuracy-matched families (MNIST-FC, GTSRB-CNN, CIFAR-CNN), each with one plain model and 3–6 adversarially trained models, are verified with α,β-CROWN on 100–215 shared properties at ε ≤ 4/255. Structural OOD: EMNIST, BTSD. Corruption OOD: PixMix, CIFAR-10-C. All 33 statistically significant ID gaps keep their order under shift. Six inversions occur, all among non-significant gaps.
  • Controlled-shift and proxy experiments. Constructed shifts with known η̂ show the bound is never violated. Across a 17-model MNIST ablation, ID CRA correlates with OOD NLL (ρ ≈ −0.9) and OOD accuracy. Selecting by ID CRA loses 0–7 points of OOD CRA.
Critical strengths
  • The empirical protocol is careful and the reporting is honest. The paper uses shared property sets, paired McNemar tests, three verifiers on MNIST, exact per-instance verdicts, and a bootstrapped regret analysis. It states clearly that η̂ = 1 on every natural axis (Table 15), that the theorems make no prediction there (App. A.8), and that the four-model families make rank preservation easy (App. E.3). This candor makes the paper easy to evaluate.
  • The question is relevant and under-studied. Whether a certificate computed on the ID test set says anything about deployment is a practical concern for the verification community. The GTSRB→BTSD observation (OOD CRA higher than ID CRA for every model) is a useful warning about query-level difficulty in benchmarks.
Critical weaknesses
  • The theory is trivial and, by the paper’s own measurement, vacuous on every natural shift. Prop. 1 is the triangle inequality. Theorems 1 and 2 follow in three lines. The paper proves these in Lean 4 and lists ~25 Lean theorems (Table 3), which adds length, not content. More important: Table 15 shows η̂(δ) = 1 for all δ ≤ 16/255 on all five natural axes. Theorem 1 then caps the erosion at 200 points (Fig. 2) and - -Theorem 2 gives a slack ≥ M. The paper acknowledges this (Sec. 6, App. A.8). So the “machine-checked theoretical framework that characterizes when ID CRA bounds OOD performance” (abstract) applies to none of the natural experiments. The only tests of the bound are constructed shifts (Sec. 5.2) where each pixel moves by exactly δ; there the bound CRA(S_Q, ε) ≥ CRA(S_P, ε + δ) is a direct restatement of ball containment and cannot fail. The theory section should be reduced to a short remark.
  • The experimental regime is far below what verification tools support, so the “verification-tractable regime” framing is not accurate. The main MNIST model has hidden layers of width 10 and 8,070 parameters (Table 4). MNIST is evaluated at ε ≤ 4/255 ≈ 0.016; the standard MNIST certification radii are 0.1 and 0.3. The CIFAR models have 58% clean accuracy, stopped early by construction. α,β-CROWN routinely verifies CIFAR ResNets and CNN-7 models with >60% clean accuracy at ε = 2/255 and 8/255. The paper’s findings may not hold at those scales, and the paper does not test them. The claim that ImageNet-scale is excluded “by the nature of the tool” does not explain why standard VNN-COMP-scale CIFAR models are excluded.
  • Rank preservation is almost guaranteed by the family design, and the paper does not show that CRA adds information over cheaper proxies. Each family has one plain model and several robust models that are statistically indistinguishable from each other (Sec. 5.2: “differences among the robust models are not significant”; App. D.3: “no two robust models are distinguishable”). The 33 preserved significant gaps are, in effect, “plain < robust” repeated across radii and axes. The six inversions are all robust-vs-robust. The same ordering is produced by empirical PGD/AutoAttack robust accuracy, or by the single bit “was adversarially trained”. The paper argues in Sec. 1 that CRA is different because it is a formal guarantee, but never compares ID CRA to ID empirical robust accuracy as a proxy for OOD metrics. Without that comparison, the model-selection claim (contribution 3) reduces to the known result that adversarial training improves calibration under shift (Augustin et al., 2020, cited by the authors).
  • The GTSRB “Plain” model is not plain. Table 6 lists Plain as TRADES (β = 6.0, ε = 0.01) and TRADES-0.01 as TRADES (β = 6.0, ε = 0.01). The two rows have the same configuration but 27% vs 58% ID CRA at 1/255 (Table 2). The footnote says “minimal TRADES configuration” without saying what differs. Either Table 6 is wrong or the two models differ in an unstated way. This must be fixed, because the GTSRB plain-vs-robust separation is a large part of the evidence.

Minor: CIFAR-10-C corruption types and severities “were not retained” (Sec. 4), so the OOD set is not reproducible. Retaining only “consensus-correct” OOD images inflates OOD CRA and may contribute to the BTSD anomaly. With n = 17 and overlapping architectures, the reported Spearman ρ values have wide intervals that are not shown in Sec. 5.3.

Questions for authors
  • Explain the GTSRB Plain vs TRADES-0.01 configurations in Table 6. What differs between them?
  • Report ID empirical robust accuracy (PGD or AutoAttack) for every model and give the same Spearman correlations with the six OOD metrics as in Sec. 5.3. Does ID CRA correlate with OOD NLL/accuracy more strongly than ID empirical robust accuracy does?
  • Report the rank-preservation and regret analysis restricted to robust-vs-robust pairs only. How many of those comparisons are significant at ID, and how many preserve order?
  • Why is MNIST evaluated at ε ≤ 4/255 and εtrain ≤ 0.03, far below the standard 0.1 / 0.3? Can the main MNIST experiment be repeated with CROWN-IBP or standard PGD models at ε = 0.1 on a 2×256 or CNN architecture?
  • Can any natural axis be found where η̂(δ) < 1 at a certified radius (e.g., a mild corruption at low severity), so that Theorem 1 makes a non-trivial prediction on real data? If not, state in the abstract that the theory does not apply to any natural shift studied.
Reviewer_eJdWOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The present paper "Does Certified Robustness Generalize? A Neural Network Verification Study of Distribution Shift" investigates whether neural networks with high certified robustness maintain these guarantees when faced with distribution shifts. For that, the authors present a simple geometric argument that states that an input will still be robust, when the induced shift still maintains a distance defined by the threat model (ℓ∞\ell_\infty norm balls of radius ϵ\epsilon) to the nearest decision boundary. In the experimental evaluation, verification experiments of small model families over MNIST, GTSRB and CIFAR-10 datasets show that model rankings are usually persisting under distribution shifts analysed through Spearman rank correlations.

Critical strengths
  • the paper studies an important question, i.e., whether certified robust accuracy persists under distribution shifts and, thus, whether it is a useful signal for model selection in the real world.
  • the theoretical arguments appear to be sound
Critical weaknesses
  • novelty is overstated. there exist several studies that investigate certified robustness under distribution shifts. the contribution of the present paper seems to be limited to an empirical investigation that studies whether certified accuracy rankings are preserved under shift. It is also questionable whether the question of whether ℓinfty\ell_infty robustness is preserved under shifts is a relevant one, or whether the more interesting question is actually, how to verify robustness against more-realistic threat models characterised by distribution shifts,
  • the theoretical result is very straightforward and uninformative for natural shifts. These may induce very large l_infty distances while inducing only minor visual changes (e.g. rotation or translation).
  • The authors only investigate CRA on instances every model classifies correctly. This makes the results questionable, since they do not reflect full-distribution certified accuracy. Further, they do not investigate whether CRA predicts OOD rankings better than simpler baselines (such as adversarial robustness or logit margins).

Important Related Works that should be mentioned include, but are not limited to: Balunović et al., “Certifying Geometric Robustness of Neural Networks,” NeurIPS, 2019. Mohapatra et al., “Towards Verifying Robustness of Neural Networks Against a Family of Semantic Perturbations,” CVPR, 2020. Kumail Alhamoud et al., “Generalizability of Adversarial Robustness Under Distribution Shifts,” TMLR, 2023. Brückner and Lomuscio, “Verification of Neural Networks Against Convolutional Perturbations via Parameterised Kernels,” AAAI, 2025.

Questions for authors
  • how do rankings change (ID and OOD) when full test sets are considered for CRA (i.e., misclassified inputs are counted as trivially non-robust)?
  • does CRA predict OOD performance better than other proxies such as adversarial attack robust accuracy or logit margins?
  • how does theorem 1 connect to distribution shifts that have small visual changes but large ℓ∞\ell_\infty norms (e.g. one-pixel translation or slight rotation)?
  • in which real world threat is persisted ℓ∞\ell_\infty robustness under distribution shifts preferable over certified robustness against the distribution shift itself?

Minor Comments:

  • L38–41 (“Modern verification methods”): Mention branch-and-bound explicitly.
  • L41 (“increasingly support convolutional and residual networks”): This support is already well established; please use more precise wording.
  • L110–125 (contributions): The contributions paragraph is very dense and hard to grasp.
  • L128–135 (verification related work): Clearly distinguish incomplete bound-propagation methods from complete branch-and-bound (and the incomplete methods used therein). Also: Abstract Interpretation is not complete (and closely related to bound propagation).
  • L130 (“Every one of them reports CRA on a fixed in-distribution test set”): verification methods solve the properties supplied to them, which need not come from an ID test set.
  • L135–140 (choice of PGD-AT and TRADES): Clarify why avoiding verifier-aware training makes differences in reported CRA attributable to training rather than differences in verification difficulty.
  • L145–153 (shift datasets and smoothing): Briefly motivate the choice of shifts and distinguish probabilistic smoothing certificates from deterministic ℓ∞\ell_\infty verification, also regarding threat models.
  • L274–279 (Table 1): Clarify why these ϵ\epsilon values and small architectures were chosen, and how representative they are of established certified-robustness benchmarks.
  • L345–355 (verification protocol): In which regard are Marabou and NNV complementary to abCROWN?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.