Cascading Robustness Verification: Toward Efficient Model-Agnostic Certification

• URL: http://arxiv.org/abs/2602.04236v1
• Date: Wed, 04 Feb 2026 05:54:08 GMT
• Title: Cascading Robustness Verification: Toward Efficient Model-Agnostic Certification
• Authors: Mohammadreza Maleki, Rushendra Sidibomma, Arman Adibi, Reza Samavi,
• Abstract summary: Incomplete verifiers scale efficiently and reduce the cost of robustness verification.<n>CRV is a model-agnostic verifier, meaning that its robustness guarantees are independent of the model's training process.<n>We show that CRV achieves equal or higher verified accuracy compared to powerful but computationally expensive incomplete verifiers.
• Score: 1.6105236927161437
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Certifying neural network robustness against adversarial examples is challenging, as formal guarantees often require solving non-convex problems. Hence, incomplete verifiers are widely used because they scale efficiently and substantially reduce the cost of robustness verification compared to complete methods. However, relying on a single verifier can underestimate robustness because of loose approximations or misalignment with training methods. In this work, we propose Cascading Robustness Verification (CRV), which goes beyond an engineering improvement by exposing fundamental limitations of existing robustness metric and introducing a framework that enhances both reliability and efficiency. CRV is a model-agnostic verifier, meaning that its robustness guarantees are independent of the model's training process. The key insight behind the CRV framework is that, when using multiple verification methods, an input is certifiably robust if at least one method certifies it as robust. Rather than relying solely on a single verifier with a fixed constraint set, CRV progressively applies multiple verifiers to balance the tightness of the bound and computational cost. Starting with the least expensive method, CRV halts as soon as an input is certified as robust; otherwise, it proceeds to more expensive methods. For computationally expensive methods, we introduce a Stepwise Relaxation Algorithm (SR) that incrementally adds constraints and checks for certification at each step, thereby avoiding unnecessary computation. Our theoretical analysis demonstrates that CRV achieves equal or higher verified accuracy compared to powerful but computationally expensive incomplete verifiers in the cascade, while significantly reducing verification overhead. Empirical results confirm that CRV certifies at least as many inputs as benchmark approaches, while improving runtime efficiency by up to ~90%.

Related papers

• ProtoDCS: Towards Robust and Efficient Open-Set Test-Time Adaptation for Vision-Language Models [32.840734752367275]
  Prototype-based Double-Check Separation (ProtoDCS) is a robust framework for OSTTA.<n>It separates csID and csOOD samples, enabling safe and efficient adaptation of Vision-Language Models to csID data.<n>ProtoDCS significantly boosts both known-class accuracy and OOD detection metrics.
  arXiv  Detail & Related papers  (2026-02-27T03:39:02Z)
• Constraint-Rectified Training for Efficient Chain-of-Thought [60.52883907721588]
  Chain-of-Thought (CoT) has significantly enhanced the reasoning capabilities of Large Language Models (LLMs)<n>While longer reasoning traces can improve answer quality and unlock abilities such as self-correction, they also incur high inference costs and often introduce redundant steps, known as overthinking.<n>Recent research seeks to develop efficient reasoning strategies that balance reasoning length and accuracy.
  arXiv  Detail & Related papers  (2026-02-13T02:13:45Z)
• PRIME: A Process-Outcome Alignment Benchmark for Verifiable Reasoning in Mathematics and Engineering [71.15346406323827]
  We introduce PRIME, a benchmark for evaluating verifiers on Process-Outcome Alignment verification.<n>We find that current verifiers frequently fail to detect derivation flaws.<n>We propose a process-aware RLVR training paradigm utilizing verifiers selected via PRIME.
  arXiv  Detail & Related papers  (2026-02-12T04:45:01Z)
• MIBP-Cert: Certified Training against Data Perturbations with Mixed-Integer Bilinear Programs [50.41998220099097]
  Data errors, corruptions, and poisoning attacks during training pose a major threat to the reliability of modern AI systems.<n>We introduce MIBP-Cert, a novel certification method based on mixed-integer bilinear programming (MIBP)<n>By computing the set of parameters reachable through perturbed or manipulated data, we can predict all possible outcomes and guarantee robustness.
  arXiv  Detail & Related papers  (2024-12-13T14:56:39Z)
• Formally Certified Approximate Model Counting [25.20597060311209]
  We present the first certification framework for approximate model counting with formally verified guarantees on the quality of its output approximation. Our approach combines: (i) a static, once-off, formal proof of the algorithm's PAC guarantee in the Isabelle/HOL proof assistant; and (ii) dynamic, per-run, verification of ApproxMC's calls to an external CNF-XOR solver using proof certificates.
  arXiv  Detail & Related papers  (2024-06-17T11:02:04Z)
• Adaptive Hierarchical Certification for Segmentation using Randomized Smoothing [87.48628403354351]
  certification for machine learning is proving that no adversarial sample can evade a model within a range under certain conditions. Common certification methods for segmentation use a flat set of fine-grained classes, leading to high abstain rates due to model uncertainty. We propose a novel, more practical setting, which certifies pixels within a multi-level hierarchy, and adaptively relaxes the certification to a coarser level for unstable components.
  arXiv  Detail & Related papers  (2024-02-13T11:59:43Z)
• Provably Cost-Sensitive Adversarial Defense via Randomized Smoothing [26.26867107261039]
  We study the problem of robust learning against adversarial perturbations under cost-sensitive scenarios.<n>Our solution introduces a provably robust learning algorithm to certify and optimize for cost-sensitive robustness.<n>In addition, we design a robust training method that improves certified cost-sensitive robustness without compromising model accuracy.
  arXiv  Detail & Related papers  (2023-10-12T21:39:16Z)
• Incremental Randomized Smoothing Certification [5.971462597321995]
  We show how to reuse the certification guarantees for the original smoothed model to certify an approximated model with very few samples. We experimentally demonstrate the effectiveness of our approach, showing up to 3x certification speedup over the certification that applies randomized smoothing of the approximate model from scratch.
  arXiv  Detail & Related papers  (2023-05-31T03:11:15Z)
• Certified Interpretability Robustness for Class Activation Mapping [77.58769591550225]
  We present CORGI, short for Certifiably prOvable Robustness Guarantees for Interpretability mapping. CORGI is an algorithm that takes in an input image and gives a certifiable lower bound for the robustness of its CAM interpretability map. We show the effectiveness of CORGI via a case study on traffic sign data, certifying lower bounds on the minimum adversarial perturbation.
  arXiv  Detail & Related papers  (2023-01-26T18:58:11Z)
• Confidence-aware Training of Smoothed Classifiers for Certified Robustness [75.95332266383417]
  We use "accuracy under Gaussian noise" as an easy-to-compute proxy of adversarial robustness for an input. Our experiments show that the proposed method consistently exhibits improved certified robustness upon state-of-the-art training methods.
  arXiv  Detail & Related papers  (2022-12-18T03:57:12Z)
• Input-Specific Robustness Certification for Randomized Smoothing [76.76115360719837]
  We propose Input-Specific Sampling (ISS) acceleration to achieve the cost-effectiveness for robustness certification. ISS can speed up the certification by more than three times at a limited cost of 0.05 certified radius.
  arXiv  Detail & Related papers  (2021-12-21T12:16:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.