arXiv:2512.11087cs.LGcs.AI2025-12NeurIPS被引 8

通过线性约束剪裁加速神经网络验证,显著减少分支定界计算量。

Clip-and-Verify: Linear Constraint-Driven Domain Clipping for Accelerating Neural Network Verification

  • 利用线性约束动态剪裁输入空间,提升验证效率。
  • 在多个基准上实现96%的子问题数量减少,验证精度达领先水平。
  • 适配主流验证框架,支持大规模模型,适合可信AI研究者使用。

当前先进的神经网络验证器表明,结合快速界界技术的分支定界(BaB)方法在处理复杂验证属性中起关键作用。本文提出线性约束驱动的剪裁框架,设计两种新算法,有效利用线性约束:1)在分支定界过程中缩小已验证或无关的输入区域;2)直接优化网络中间层的界。该过程新颖地利用界传播中常见的线性约束,并可扩展至其他来源约束。通过专用GPU计算高效处理线性约束,无需昂贵外部求解器,适用于大规模网络。所提出的验证方法Clip-and-Verify在多个基准上持续收紧界,显著降低分支定界中的子问题数量。实验显示,在部分场景下子问题减少达96%;同时在多个基准上实现最优的已验证准确率。Clip-and-Verify已集成于α,β-CROWN验证器(http://abcrown.org),为VNN-COMP 2025冠军。代码开源于https://github.com/Verified-Intelligence/Clip_and_Verify。

原文摘要 · Abstract (English)

State-of-the-art neural network (NN) verifiers demonstrate that applying the branch-and-bound (BaB) procedure with fast bounding techniques plays a key role in tackling many challenging verification properties. In this work, we introduce the linear constraint-driven clipping framework, a class of scalable and efficient methods designed to enhance the efficacy of NN verifiers. Under this framework, we develop two novel algorithms that efficiently utilize linear constraints to 1) reduce portions of the input space that are either verified or irrelevant to a subproblem in the context of branch-and-bound, and 2) directly improve intermediate bounds throughout the network. The process novelly leverages linear constraints that often arise from bound propagation methods and is general enough to also incorporate constraints from other sources. It efficiently handles linear constraints using a specialized GPU procedure that can scale to large neural networks without the use of expensive external solvers. Our verification procedure, Clip-and-Verify, consistently tightens bounds across multiple benchmarks and can significantly reduce the number of subproblems handled during BaB. We show that our clipping algorithms can be integrated with BaB-based verifiers such as $α,β$-CROWN, utilizing either the split constraints in activation-space BaB or the output constraints that denote the unverified input space. We demonstrate the effectiveness of our procedure on a broad range of benchmarks where, in some instances, we witness a 96% reduction in the number of subproblems during branch-and-bound, and also achieve state-of-the-art verified accuracy across multiple benchmarks. Clip-and-Verify is part of the $α,β$-CROWN verifier (http://abcrown.org), the VNN-COMP 2025 winner. Code available at https://github.com/Verified-Intelligence/Clip_and_Verify.

神经网络验证分支定界线性约束可信AI

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。