Stress-Testing Neural Network Verifiers with Provably Robust Instances David Troxell, Yulia Alexandr, Sofia Hunt, Stephanie Lei, Guido Montúfar Abstract Neural network verifiers aim to provide formal guarantees on model behavior, but existing verification benchmarks are fundamentally limited by their lack of ground-truth labels. As a result, verifier evaluation relies on indirect heuristics, which prevents exact scoring and systematic study of verifier failure modes. We address this gap by introducing a reusable framework for generating verification instances whose ground-truth robustness labels are known a priori through analytic construction. Our framework led to the discovery of multiple numeric tolerance concerns and an implementation bug in popular verifiers, highlighting the need for ground-truth labels. Additionally, to systematically study verifier failure modes, we introduce the verification Difficulty Profile, a collection of estimable quantities capturing distinct sources of instance hardness. Using our framework and these profiles, we evaluate five state-of-the-art verifiers and show that different instances stress distinct aspects of the verification pipeline. We show that these results can aid the future development of verifiers as they provide actionable targets for improving numerical reliability, relaxation quality, and search behavior. Our code is publicly available: https://github.com/dtroxell19/VeriStressGT.git . 1 Introduction Deep learning systems are rapidly being integrated into safety-critical applications in society, including AI-enabled medical devices, self-driving vehicles, power grid balancing for energy systems, and quality control for chemical processes [ 20 , 19 , 29 ] . However, these systems often exhibit fragile and unpredictable behavior as small input perturbations can induce large and unintended changes in outputs [ 4 , 18 , 16 ] . In applications where unexpected fluctuations in model behavior have dire consequences, such instability raises a fundamental question of how to guarantee that a trained model behaves safely under all admissible inputs. Neural network verification aims to answer this question by providing formal guarantees on model behavior. Given a trained model, an admissible input set, and a desired property, verifier systems attempt to certify whether the property holds for all inputs in the set. This work focuses on robustness specifications, where the goal is to certify stable model behavior under bounded input perturbations. A wide array of verification techniques have been developed in recent years, including Satisfiability Modulo Theory (SMT) and Mixed Integer Programming (MIP) approaches [ 10 , 22 ] , convex relaxation methods [ 25 ] , and scalable branch-and-bound frameworks such as \alpha,\beta -CROWN [ 24 , 27 ] . Modern verifiers can now handle networks with millions of parameters and increasingly complex architectures. However, despite algorithmic progress, the evaluation of neural network verifiers themselves remains fundamentally limited. Specifically, existing benchmarks generally lack ground-truth labels indicating whether a verification instance is truly robust or non-robust, and they offer little characterization of instance difficulty beyond verifier runtime. These limitations have three primary, direct consequences: First, without ground-truth labels, verifier evaluation currently relies on indirect heuristics. For example, VNN-COMP, the annual competition for neural network verification, uses majority voting when verifiers disagree on a model instance due to numerical tolerance issues [ 12 ] . Additionally, when no verifier finds a valid robustness counterexample and instead claims robustness or times out, the instance is treated as robust under an assumption of verifier soundness [ 12 ] . However, this assumption may be more fragile than anticipated as recent works have found bugs and imprecisions in various verifier implementations [ 31 , 9 , 32 ] . Second, without ground-truth labels, benchmarks cannot systematically stress-test the ability of verifiers to certify increasingly difficult robust instances. Non-robust instances are often quickly exposed by adversarial search methods such as projected gradient descent, making them relatively easier to classify [ 17 ] . The harder and more informative regime is robust-but-difficult instances, where a verifier must prove that no counterexample exists. Recent work makes existing benchmarks harder while preserving their original ground truth by destabilizing ReLU activations [ 15 ] . However, this approach inherits labels from the input benchmark and only varies one difficulty mechanism. Benchmarks therefore still lack a general way to generate robust instances with verifier-independent labels and varied, targeted knobs for different bottlenecks. Third, current verifier benchmark outcomes alone often provide limited diagnostic information about why a verifier succeeds, fails, or times out. Prior work has shown that performance is related to coarse factors such as network architecture and input dimension [ 26 ] . However, these high-level factors provide less insight into whether a verifier is limited by loose relaxations, complex local geometry, or other bottlenecks. Without targeted instances that isolate such bottlenecks, it is also difficult to evaluate verifiers designed to address a specific failure mode. In this work, we address these gaps by introducing VeriStress-GT (Verifier Stress-Testing via Ground Truth), a modular and re-usable framework to generate benchmark instances for neural network verification with analytically proven ground-truth robustness labels. Moreover, we design these constructions to have controllable difficulty, enabling gradual systematic stress-testing of verification methods for the first time. To guide this process and better analyze verifier failure modes, we introduce the Difficulty Profile, a collection of estimable quantities that characterize verification instance hardness. More broadly, this work reframes verification benchmarking from heuristic evaluation to controlled, ground-truth experimentation. Our primary contributions are as follows: • We introduce VeriStress-GT, to our knowledge the first reusable framework for generating neural network verification instances with verifier-independent ground-truth robustness labels and controllable difficulty for systematic verifier stress-testing. • We propose the verification instance Difficulty Profile, a unified framework for characterizing verification instance hardness. We show that the profile components enable the systematic evaluation of verifier scalability and failure modes. • We evaluate five state-of-the-art verifiers using VeriStress-GT and Difficulty Profiles, revealing distinct limitations across verification paradigms and identifying previously unreported numerical and implementation issues. 2 Robust Constructions for Neural Network Verification Benchmarking We first define the robustness verification instance as the tuple (f,x_{0},y,\mathcal{B}_{\epsilon}) consisting of a trained neural network f:\mathbb{R}^{d}\to\mathbb{R}^{c} , a nominal input x_{0}\in\mathbb{R}^{d} with correct class y\in[c] , and a perturbation set \mathcal{B}_{\epsilon}(x_{0})=\{x:\|x-x_{0}\|_{p}\leq\epsilon\} . In this work we specifically study verification for network robustness; in other words, does f classify every input in \mathcal{B}_{\epsilon}(x_{0}) identically to x_{0} ? Define the per-class margin functions \mu_{k}(x)=f_{y}(x)-f_{k}(x) for k\in[c] , k\neq y and the overall margin \mu(x)=\min\limits_{k\neq y}\mu_{k}(x) . Then, we state that f is provably robust at x_{0} if and only if \min\limits_{x\in\mathcal{B}_{\epsilon}(x_{0})}\mu(x)>0 . Rather than defining a fixed set of benchmark instances, VeriStress-GT defines a novel collection of constructors, each of which produces verification instances with analytically proven robustness labels. Each constructor targets a particular architectural class or verifier bottleneck, allowing the benchmark to probe different sources of verification difficulty. Figure 1 provides a high-level overview of the constructors and framework design principles. We briefly describe each of the constructors within the framework below and include constructor details in Appendix A . Figure 1: High-level overview of VeriStress-GT, a benchmark for stress-testing neural network verifiers. Benchmark instances are generated via various constructors, or methods to generate provably robust instances. New constructors can easily be added to the framework, and each constructor admits difficulty parameters that can gradually increase verification difficulty while retaining robustness. 2.1 ReLU Network Constructors Throughout this section, let \sigma(t)=\max\{t,0\} denote the ReLU activation function applied elementwise. A ReLU MLP is a composition of affine maps and ReLU, producing logits f_{1}(x),\dots,f_{c}(x) . Exact-Radius via Mixed-Integer Linear Programming (MILP). We generate near-boundary robust instances by computing the network’s exact robustness radius using a standard mixed-integer linear programming (MILP) encoding of ReLU networks [ 21 ] . Specifically, for each target class k\neq y , we solve a mixed-integer linear program that minimizes the \ell_{\infty} perturbation such that f_{k}(x)\geq f_{y}(x) . Let t_{k}^{\star} be the optimal perturbation for class k , and define r^{\star}=\min_{k\neq y}t_{k}^{\star} . Then any perturbation radius \epsilon0 for all k\neq y , then f is robust with margin at least \gamma . For \ell_{\infty} perturbations, the set \mathcal{B}_{\epsilon}(x_{0}) is an axis-aligned box, so the condition x\in\mathcal{B}_{\epsilon}(x_{0}) decomposes into independent interval constraints on each input coordinate. This allows \Pi to be built from one-dimensional ReLU hinge functions applied separately to each coordinate. To see this in one dimension, choose two scalars \alpha and \beta such that [x_{0}-\epsilon,x_{0}+\epsilon]\subseteq[\alpha,\beta] . Then the scalar map x\mapsto t+\sigma(\alpha-x)+\sigma(x-\beta) is equal to t throughout the perturbation interval. Applying this coordinatewise gives a ReLU network that collapses the entire input box to a single point in the latent dimension. The primary parameter used to stress-test verifiers is therefore the depth and width of the downstream network \psi , which can be made arbitrarily large while preserving the same ground-truth robustness label. Mutually Exclusive Activation Patterns (MEAP). Most relaxation-based verifier implementations initially treat network neurons independently before performing additional computationally intensive refinement. Therefore, to stress-test verifiers, MEAP constructs a ReLU network whose hidden units are individually unstable (i.e., switch between active and inactive as x varies within \mathcal{B}_{\epsilon}(x_{0}) ) but are coupled by geometric constraints. Specifically, neurons are organized into pairs such that, for every input in the perturbation set, each pair contains at least one active neuron. To embed this geometric constraint, the network first forms P pairs of affine preactivations. For each p\in[P] , let z_{p,1}(x)=w_{p}^{\top}x+b_{p,1} and z_{p,2}(x)=-w_{p}^{\top}x+b_{p,2} . Each pair is then aggregated by r_{p}(x)=\max\{\sigma(z_{p,1}(x)),\sigma(z_{p,2}(x))\} , and the target logit is defined as the minimum over pair scores: f_{y}(x)=\min_{p\in[P]}r_{p}(x),\qquad f_{k}(x)=0\quad\text{for all }k\neq y. (1) This function is piecewise linear and can be implemented as a ReLU network using standard identities for pairwise maxima and minima. The robustness follows from choosing biases b_{p,1} and b_{p,2} such that, for every x\in\mathcal{B}_{\epsilon}(x_{0}) , at least one preactivation in each pair is positive. Equivalently, each pair satisfies r_{p}(x)>0 throughout the perturbation set. Hence f_{y}(x)>0=f_{k}(x) for all k\neq y , certifying robustness. Appendix A.2 gives the full construction and proof. Input-Corner Stress. The input-corner constructor creates ReLU networks whose robustness certificate is given by finite corner evaluation. Let \mathcal{B}_{\epsilon}(x_{0}) be an \ell_{\infty} box, suppose the logits depend only on an active set A\subseteq[d] of d_{act} input coordinates. We set the correct-class logit to be constant, f_{y}(x)=0 , and define each competitor logit as f_{k}(x)=h_{k}(x)-\beta_{k} , where h_{k} is convex on the active-coordinate box. Then the per-class margin \mu_{k}(x)=f_{y}(x)-f_{k}(x)=\beta_{k}-h_{k}(x) is concave, so its minimum over the box is attained at an extreme point. Let \mathcal{V}_{\epsilon}(x_{0};A)=\{x_{0}+\epsilon s:s_{i}\in\{-1,+1\}\ \text{for }i\in A,s_{i}=0\ \text{for }i\notin A\} denote the active-coordinate corners. Choosing \beta_{k}=\max_{v\in\mathcal{V}_{\epsilon}(x_{0};A)}h_{k}(v)+\gamma implies \mu_{k}(x)\geq\gamma for all x\in\mathcal{B}_{\epsilon}(x_{0}) , so the instance is robust with margin at least \gamma . A ReLU implementation takes h_{k}(x)=\sum_{j=1}^{J}c_{k,j}\sigma(a_{j}^{\top}x+b_{j}) with c_{k,j}\geq 0 , since nonnegative sums of ReLU hinges are convex. The construction can nevertheless be difficult for standard verifiers as many hinges can be placed near instability at x_{0} , making local relaxations loose, while the true proof relies on the fact that convex functions attain their maximum over a box at a corner. The main difficulty parameters are the number of hinges J , active dimension d_{act} , hinge scale \|a_{j}\|_{1} , and margin \gamma . Appendix A.3 gives the formal corner certificate and implementation details. 2.2 CNN Constructors For CNN constructors, inputs are tensors x\in\mathbb{R}^{C_{\mathrm{in}}\times H_{\mathrm{in}}\times W_{\mathrm{in}}} . We write Z for an intermediate feature map and use \star to denote convolution with padding and stride fixed by the architecture. A convolutional layer with filters \{\mathcal{W}_{i}\}_{i=1}^{K} and biases \{b_{i}\}_{i=1}^{K} produces preactivations u_{hw}^{(i)}=(\mathcal{W}_{i}\star Z)_{hw}+b_{i} at output channel i and spatial location (h,w) , followed by a coordinatewise activation such as ReLU. Deep Contractive CNN. This constructor attains robustness by forcing perturbations to contract through depth. We write the feature extractor as \Phi=C_{D}\circ C_{D-1}\circ\cdots\circ C_{1}\circ P , where P is an optional front-end map and C_{1},\dots,C_{D} are contractive convolutional blocks. Let L_{\mathrm{front}} denote the \ell_{\infty} Lipschitz constant of P , with L_{\mathrm{front}}=1 if no front-end map is used. Each block C_{\ell} consists of a convolutional layer followed by a 1 -Lipschitz pointwise activation function and is normalized to have induced \ell_{\infty} Lipschitz constant of at most \lambda<1 . Intuitively, then, each layer in P may expand perturbations by at most L_{\mathrm{front}} while each subsequent block shrinks the worst-case perturbations by a factor of at most \lambda . The formal Lipschitz certificate in Appendix A.4 shows that: \|\Phi(x)-\Phi(x^{\prime})\|_{\infty}\leq L_{\mathrm{front}}\lambda^{D}\|x-x^{\prime}\|_{\infty}. (2) We set the correct-class logit to be a large constant plus a centered perturbation term f_{y}(x)=\Gamma+w_{y}^{\top}(\Phi(x)-\Phi(x_{0})) and set each incorrect class logit equal to 0 . Therefore, over the perturbation set \mathcal{B}_{\epsilon}(x_{0}) , f_{y} can decrease by at most \|w_{y}\|_{1}L_{\mathrm{front}}\lambda^{D}\epsilon . Choosing \Gamma>\|w_{y}\|_{1}L_{\mathrm{front}}\lambda^{D}\epsilon therefore certifies robustness on \mathcal{B}_{\epsilon}(x_{0}) . The main difficulty parameters are the depth D , contraction rate \lambda , spatial dimension, front-end Lipschitz constant L_{\mathrm{front}} , and margin slack \Gamma-\|w_{y}\|_{1}L_{\mathrm{front}}\lambda^{D}\epsilon . Paired-Bias CNN. The paired-bias CNN construction is a convolutional analogue of MEAP since it involves creating pairs of convolutional channels whose ReLU activations may be unstable, but whose difference is globally nonnegative. The construction may be applied after arbitrary upstream convolutional layers since the certificate holds for every possible value of the shared convolutional response. Let Z=\Psi(x) denote the feature map produced by this upstream network. For each filter pair i\in[P] , two channels share the same convolutional filter \mathcal{W}_{i} but have ordered biases b_{i}>c_{i} . At the layer where the construction is applied, let s^{(i)}=\mathcal{W}_{i}\star Z\in\mathbb{R}^{H_{\mathrm{sp}}\times W_{\mathrm{sp}}} denote the shared convolutional response for pair i , where H_{\mathrm{sp}} and W_{\mathrm{sp}} are the height and width of the feature map. Therefore, at spatial location (h,w) , the paired ReLU inputs are s_{hw}^{(i)}+b_{i} and s_{hw}^{(i)}+c_{i} . Since the ReLU function is monotone and b_{i}>c_{i} , we have that \sigma(s+b_{i})-\sigma(s+c_{i})\geq 0\;\forall s\in\mathbb{R} . The target logit averages these nonnegative differences over all pairs and spatial locations: f_{y}(x)=\Gamma+\frac{1}{PH_{\mathrm{sp}}W_{\mathrm{sp}}}\sum_{i=1}^{P}\sum_{h,w}\left[\sigma(s_{hw}^{(i)}+b_{i})-\sigma(s_{hw}^{(i)}+c_{i})\right],\qquad f_{k}(x)=0\quad\text{for all }k\neq y. (3) Thus f_{y}(x)\geq\Gamma>0 for all inputs, giving a global robustness certificate. The construction becomes difficult when both channels in many pairs are unstable over the perturbation set. A relaxation that treats \sigma(s+b_{i}) and \sigma(s+c_{i}) independently may produce a negative lower bound on their difference, even though the true difference is always nonnegative because the two ReLUs share the same scalar s . The number of pairs P , size of feature map H_{\mathrm{sp}}\times W_{\mathrm{sp}} , bias gap b_{i}-c_{i} , and margin constant \Gamma control the accumulated relaxation error. Appendix A.5 gives the formal robustness proof. 2.3 Attention Module Constructors For attention module-based constructors, inputs are sequences X\in\mathbb{R}^{n\times d_{\mathrm{tok}}} , with rows x^{(i)}\in\mathbb{R}^{d_{\mathrm{tok}}} as tokens. Perturbations are measured in the entrywise norm \|X-X_{0}\|_{\infty}=\max_{i,j}|X_{ij}-(X_{0})_{ij}| . We write Q(X)=XW_{Q} , K(X)=XW_{K} , and V(X)=XW_{V} for the query, key, and value projections, where W_{Q}\in\mathbb{R}^{d_{\mathrm{tok}}\times d_{q}} , W_{K}\in\mathbb{R}^{d_{\mathrm{tok}}\times d_{k}} , and W_{V}\in\mathbb{R}^{d_{\mathrm{tok}}\times d_{v}} are learned matrices. Fixed-Ordering Softmax Attention. For single-head softmax attention, robustness can be certified by showing that the score ordering is stable and the resulting attention output cannot drift enough to change the class. Define the score kernel M={W_{Q}W_{K}^{\top}}/{\sqrt{d_{k}}} , and let S(X)=XMX^{\top} with S_{ij}(X)=(x^{(i)})^{\top}Mx^{(j)} . The attention output is \mathrm{Attn}(X)=A(X)XW_{V} , where A(X) is the row-wise softmax of S(X) , and the full classifier is f=h\circ\mathrm{Attn} for some downstream head h . Let \pi_{i}^{\star}=\argmax_{j}S_{ij}(X_{0}) denote the nominal row-wise score maximizer in row i , assuming it is unique, and define the score gaps \Delta_{ij}=S_{i,\pi_{i}^{\star}}(X_{0})-S_{ij}(X_{0})>0 for j\neq\pi_{i}^{\star} . A bilinear expansion of the score differences, derived in Appendix A.6 , gives: \left|\left[S_{i,\pi_{i}^{\star}}(X)-S_{ij}(X)\right]-\Delta_{ij}\right|\leq\epsilon C_{ij}, (4) for all \|X-X_{0}\|_{\infty}\leq\epsilon , where C_{ij} depends on \|M\|_{\mathrm{op}} , the nominal token norms, d_{\mathrm{tok}} , and \epsilon . If \Delta_{ij}>\epsilon C_{ij} for every i and j\neq\pi_{i}^{\star} , then row-wise score maximizers remain fixed throughout \mathcal{B}_{\epsilon}(x_{0}) . Appendix A.6 also provides a perturbation bound for the attention output: there exists a constant L_{\mathrm{attn}} such that \|\mathrm{Attn}(X)-\mathrm{Attn}(X_{0})\|_{F}\leq\sqrt{n}L_{\mathrm{attn}}\epsilon\;\forall X\in\mathcal{B}_{\epsilon}(X_{0}) . Letting \mu(X_{0})=\min_{k\neq y}\left(f_{y}(X_{0})-f_{k}(X_{0})\right) denote the nominal classification margin, if each logit of the downstream head h is L_{h} -Lipschitz with respect to the Frobenius norm, then each class-wise margin can decrease at most by 2L_{h}\sqrt{n}L_{\mathrm{attn}}\epsilon . Hence, if \mu(X_{0})>2L_{h}\sqrt{n}L_{\mathrm{attn}}\epsilon , then f is robust on \mathcal{B}_{\epsilon}(X_{0}) . Dominant-Key Linear Attention. This constructor uses linear attention, where the softmax score kernel is replaced by a nonnegative feature-map inner product. Let q^{(i)}(X)=Q(X)[i,:] and k^{(j)}(X)=K(X)[j,:] . For a nonnegative feature map \phi with positive row sums, define: w_{ij}(X)=\langle\phi(q^{(i)}(X)),\phi(k^{(j)}(X))\rangle\geq 0. (5) The normalized attention weights are then \alpha_{ij}(X)=\frac{w_{ij}(X)}{\sum_{\ell=1}^{n}w_{i\ell}(X)}, and the module’s output is: \mathrm{Attn}_{\mathrm{lin}}(X)[i,:]=\sum_{j=1}^{n}\alpha_{ij}(X)V(X)[j,:]. (6) Instead of certifying softmax score-order stability, this constructor enforces a dominant key per query row. Fix a dominant key j_{i}^{\star} for each row and suppose that throughout the perturbation set we have: w_{ij_{i}^{\star}}(X)\geq\rho_{i}\sum_{j\neq j_{i}^{\star}}w_{ij}(X). (7) This condition says that, for query row i , the unnormalized attention weight assigned to key j_{i}^{\star} is at least \rho_{i} times the total weight assigned to all other keys. Letting \rho=\min_{i}\rho_{i} , we therefore have that row i assigns at least \frac{\rho_{i}}{(1+\rho_{i})} normalized attention mass to j_{i}^{\star} . Since the attention output is a weighted average of value vectors, the row output remains close to the value vector V(X)[j_{i}^{\star},:] associated with the dominant key. The perturbation proof in Appendix A.7 shows: \|\mathrm{Attn}_{\mathrm{lin}}(X)-\mathrm{Attn}_{\mathrm{lin}}(X_{0})\|_{2,\infty}\leq\frac{2}{1+\rho}D_{V}(X_{0})+\Big(1+\frac{2}{1+\rho}\Big)\epsilon\sqrt{d_{\mathrm{tok}}}\|W_{V}\|_{\mathrm{op}}, (8) where D_{V}(X_{0})=\max_{i}\max_{j\neq j_{i}^{\star}}\|V(X_{0})[j,:]-V(X_{0})[j_{i}^{\star},:]\|_{2} is the largest nominal distance, over query rows, between the value vector associated with the dominant key j_{i}^{\star} and any other. Thus, if f=h\circ\mathrm{Attn}_{\mathrm{lin}} , each logit of h is L_{h} -Lipschitz in Frobenius norm, and the nominal margin \mu(X_{0}) is larger than twice the induced logit drift, then the classifier is robust. For this constructor, difficulty can be controlled through the dominance ratio \rho , value spread D_{V}(X_{0}) , and sequence length. 2.4 Polynomial Network Constructor The polynomial network constructor generates candidate robust instances by explicitly controlling the geometry of the decision boundary. We consider polynomial classifiers, such as feedforward networks with affine layers and monomial activations, so that each logit is a polynomial in the input. In the binary classification case, let \mu(x)=f_{1}(x)-f_{2}(x) be the margin polynomial and let D=\{x:\mu(x)=0\} be the decision boundary. Thus D is a real algebraic hypersurface. The constructor samples a smooth boundary point p\in D , chooses a norm-adapted normal direction u(p) , and places the nominal input at x_{0}=p+(\epsilon+\delta)u(p) , where \delta>0 is a boundary buffer. The sampled point p is therefore a known boundary point just outside the perturbation set B_{\epsilon}(x_{0}) . The local placement step creates a near-boundary instance, but the ground-truth robustness label comes from a global separation check certifying that B_{\epsilon}(x_{0})\cap D=\emptyset . This rules out another branch or component of the decision boundary entering the perturbation set. When the check succeeds, \mu has constant sign on B_{\epsilon}(x_{0}) , so the instance is robust. The buffer \delta controls proximity to failure: decreasing \delta makes the perturbation set nearly touch the decision boundary, forcing verifiers to certify a small positive separation from a curved polynomial hypersurface. The main difficulty parameters are the input dimension, polynomial degree, hidden width, and boundary buffer \delta . Appendix A.8 gives the full construction, boundary-sampling procedure, and nearest-boundary certificate. 3 The Verification Instance Difficulty Profile In addition to the VeriStress-GT framework, we move towards a quantifiable characterization of verification instance difficulty via Difficulty Profiles. Such quantification allows one to compare instances beyond binary robust and non-robust labels. The components of the Difficulty Profile are chosen to satisfy design principles ensuring computability, applicability, and interpretability (see Appendix E for an explanation of design principles and candidate components tested). Based on the taxonomy of verifier certificate styles (Appendix C ) and design principles, we define the profile: Definition 1 . The difficulty profile of a verification instance (f,x_{0},y,\mathcal{B}_{\epsilon}) is the tuple: \mathbf{D}(f,x_{0},y,\mathcal{B}_{\epsilon})=\bigl(\widehat{M}_{\min},\;G_{\mathrm{IBP}},\;U,\;A_{\tau},\;d_{\mathrm{eff}}\bigr). (9) Each component, defined below, targets a different axis of verification difficulty: \widehat{M}_{\min} measures the amount of empirical margin slack to certify, G_{\mathrm{IBP}} measures how much of this slack is lost under a coarse interval relaxation, U measures the fraction of nonlinear units whose phase remains ambiguous over the input set, A_{\tau} measures the local regions encountered in the input set, and d_{\mathrm{eff}} measures the effective dimensionality of the input directions along which the margin is sensitive. Component 1: Minimum Margin ( \widehat{M}_{\min} ). Proximity to violation is a basic, intuitive source of verification difficulty as instances with small positive margin may require substantial branching or bound refinement. Since \min_{x\in\mathcal{B}_{\epsilon}(x_{0})}\mu(x) is generally nonconvex and intractable, we estimate it via a sampling procedure. Let \mathcal{S}=\{x_{1},\dots,x_{N}\}\subset\mathcal{B}_{\epsilon}(x_{0}) denote a set of profiling samples, drawn from a mixture of uniform and boundary-biased samples. Then, we define: \widehat{M}_{\min}:=\min_{x_{i}\in\mathcal{S}}\mu(x_{i}) (10) A small, positive \widehat{M}_{\min} suggests that the instance is close to a counterexample, while \widehat{M}_{\min}<0 indicates that sampling already found one. We note that \widehat{M}_{\min} is not designed to be a certificate of robustness, but rather a verifier-agnostic proxy for proximity to the decision boundary. Component 2: IBP Relative Gap ( G_{\mathrm{IBP}}) . Relaxation-based verifiers certify robustness via tractable lower bounds on \mu(x) . We therefore use IBP as an efficient, architecture-agnostic proxy for relaxation looseness. Let L_{\mathrm{IBP}} denote the IBP lower bound over \mathcal{B}_{\epsilon}(x_{0}) . Define the relative gap as: G_{\mathrm{IBP}}:=\frac{\widehat{M}_{\min}-L_{\mathrm{IBP}}}{|\widehat{M}_{\min}|+\eta}, (11) where \eta>0 is a small numerical stability constant. The numerator estimates the margin slack lost by IBP by the best sampled margin, while the denominator normalizes by the empirical margin scale. Hence larger G_{\mathrm{IBP}} indicates increased instance difficulty, particularly for relaxation-based verifiers. Component 3: Unstable Fraction ( U ). The unstable fraction measures how many nonlinear neurons cannot be treated as fixed or locally affine over \mathcal{B}_{\epsilon}(x_{0}) . For ReLU networks, this is the fraction of neurons whose IBP pre-activation interval [\ell_{j},u_{j}] crosses zero, i.e., \ell_{j}<0\tau for a fixed threshold \tau>0 . Let \mathcal{J} denote the set of nonlinear coordinates. We define: U:=\frac{1}{|\mathcal{J}|}\sum_{j\in\mathcal{J}}\mathbbm{1}_{\{\omega_{j}>\tau\}}. (12) For ReLU neurons, this reduces exactly to the unstable-neuron fraction. Larger U indicates that more units require nontrivial relaxation or case splitting. Component 4: Local-Region Complexity ( A_{\tau} ). The unstable fraction U measures individually nonlinear coordinates, but not how many distinct local behaviors are realized in \mathcal{B}_{\epsilon}(x_{0}) . To capture this, we view local-region complexity as an affine-covering problem. For tolerance \delta>0 , define: N_{\mathrm{aff}}(\delta):=\min\Bigl\{m:\mathcal{B}_{\epsilon}(x_{0})\subseteq\textstyle\bigcup_{i=1}^{m}U_{i},\;\exists(a_{i},b_{i})\text{ s.t. }\sup\limits_{x\in U_{i}}|\mu(x)-a_{i}^{\top}x-b_{i}|\leq\delta\Bigr\}, (13) where the U_{i} range over convex subsets of \mathcal{B}_{\epsilon}(x_{0}) . Let L_{c}:=\sup\limits_{x\in\mathcal{B}_{\epsilon}(x_{0})}\sup\limits_{\xi\in\partial_{c}\mu(x)}\|\xi\|_{p,*} denote a local Lipschitz constant for the margin over \mathcal{B}_{\epsilon}(x_{0}) , where \partial_{c}\mu(x) is the Clarke subdifferential and \|\cdot\|_{p,*} is dual to \|\cdot\|_{p} . Set A_{\tau}^{\star}:=\log N_{\mathrm{aff}}(\tau\epsilon L_{c}) . Therefore, A_{\tau}^{\star} counts how many affine functions are needed to approximate the margin over the perturbation set with resolution \tau . For ReLU networks, this corresponds to an effective count of affine regions, while for networks with smooth activation functions it counts the number of local Taylor approximations needed to approximate the curved margin landscape. The following proposition motivates our empirical estimator by showing that affine-cover complexity is governed by how much the normalized gradient can vary over \mathcal{B}_{\epsilon}(x_{0}) : Proposition 2 (Smooth affine-cover bound) . Assume that \mu(x) is differentiable on \mathcal{B}_{\epsilon}(x_{0}) and that its gradient is \beta -Lipschitz. Let \widetilde{\beta}:=\frac{\beta\epsilon}{L_{c}(\mu)} be the normalized gradient-variation scale. Then, up to the standard covering-number constant for the chosen norm, \smash{A_{\tau}^{\star}\leq d\log\big(1+\sqrt{\smash[b]{{2\widetilde{\beta}}/{\tau}}}\big)}. See Appendix B for the proof. Directly estimating the global gradient-Lipschitz scale \widetilde{\beta} is conservative in practice, so we instead measure the realized variation in local linear behavior by sampling normalized gradients. For each x_{i}\in\mathcal{S} , let q_{\tau}(x_{i}):=\operatorname{Quantize}_{\tau}(\nabla\mu(x_{i})/L_{c}) , where \operatorname{Quantize}_{\tau}(v) denotes coordinatewise quantization of v onto a grid of width \tau . We define: A_{\tau}:=\log\left|\{q_{\tau}(x_{i}):x_{i}\in\mathcal{S}\}\right|. (14) A_{\tau} is a sampled log-count of distinct normalized local affine behaviors, as it estimates the realized local complexity suggested by the affine-cover definition. Larger A_{\tau} indicates more heterogeneous local behavior, making coarse relaxations, abstractions, or partitions less likely to remain tight. Component 5: Effective Gradient dimensionality ( d_{\mathrm{eff}} ). Even when the margin is sensitive to perturbations, the structure of this sensitivity matters. If sensitivity is concentrated in a few input coordinates, splitting or search may isolate it quickly, but if it is spread across many, the instance is effectively high-dimensional. Let \nabla\mu(x) denote the input gradient of the margin where it exists, using any measurable subgradient at non-smooth points. Define the average effective gradient dimension: d_{\mathrm{eff}}:=\frac{1}{|\mathcal{S}|}\sum_{x_{i}\in\mathcal{S}}\frac{\|\nabla\mu(x_{i})\|_{1}^{2}}{\|\nabla\mu(x_{i})\|_{2}^{2}+\eta}, (15) where \eta>0 is a small constant for numerical stability. This quantity is related to the Participation Ratio (PR) for measuring dimensionality [ 7 ] , and is near 1 when the gradient is concentrated on one coordinate and near r when it is spread evenly across r coordinates. Larger d_{\mathrm{eff}} therefore indicates more distributed margin sensitivity, which is especially relevant for \ell_{\infty} perturbations since the first-order margin decrease scales with \epsilon\|\nabla\mu(x)\|_{1} . 4 Numerical Experiments and Verification Study We evaluate 5 top-scoring verifiers on 225 VeriStress-GT instances spanning all constructors in Section 2 , plus two external robustness benchmarks: MNIST \_ fc, with fully connected ReLU networks trained on MNIST [ 2 , 14 ] , and oval 21 , with ReLU CNNs trained on MNIST and CIFAR-related tasks [ 2 , 13 ] . The VeriStress-GT instances form a parameter-diverse stress-test suite, though the framework can generate unlimited instances. We compute Difficulty Profile estimates for all instances. All experiments were run on an Intel Xeon Gold 6152 CPU server with 32 CPU cores, using per-instance timeouts of 600 seconds for VeriStress-GT and 360 seconds for external benchmarks. Appendix F gives framework instantiation details and aggregate verifier outcomes. Figure 2 summarizes verifier runtimes, while Figure 3 shows how Difficulty Profile components and interactions discriminate verifier timeouts. We highlight three main takeaways: Figure 2: Runtime outcomes for 5 verifiers on VeriStress-GT constructors and two external benchmarks, shown in the last two rows. Average runtimes include timeouts of 600 seconds for VeriStress-GT and 360 seconds for external benchmarks. Fractions report correct results over total instances; missing runtimes indicate unsupported computation graphs. 1. Ground-truth labels reveal incorrect robustness claims. Despite all instances in this instantiation of the VeriStress-GT framework containing analytic proofs of UNSAT (i.e., robust) labels, multiple verifiers return false SAT (i.e., non-robust) claims. Many of these incorrect claims can primarily be attributed to numerical tolerance limitations. For instance, setting the perturbation radius \epsilon equal to 0.999 times the exact robustness radius computed via the MILP approach led to such SAT claims for a number of verifiers. However, when separately testing verifiers with an Exact-Radius MILP construction containing provably non-robust instances (i.e., a perturbation radius \epsilon larger than the network’s exact adversarial radius), we discovered a bug in a popular verifier’s handling of disjunctive output constraints, leading to false UNSAT claims which have since been corrected after collaboration with developers (see Appendix D for details). Incorrect claims for verification can be impactful; false UNSAT claims can mislead practitioners into believing a model is certifiably safe when it is not, and false SAT claims distort verifier evaluation. VeriStress-GT helps expose these failures and highlights the need for a careful review of numerical tolerance limits. 2. Difficulty Profiles help make verifier timeouts diagnosable. Without Difficulty Profiles, analysis generally ends at measuring the number of timeouts; some instances are certified, others are not, and the reason largely remains opaque. Difficulty Profiles turn these outcomes into diagnosable failure modes. For example, Figures 5 and 6 in Appendix F show that the final 16 MNIST \_ fc instances have G_{\mathrm{IBP}}\geq 2\times 10^{5} , several orders of magnitude larger than the remaining MNIST \_ fc instances and the corresponding values in VeriStress-GT or oval 21 , suggesting extreme interval-relaxation looseness as the dominant obstruction. In oval 21 , instances 10 – 16 are certified by at most two verifiers each and all have d_{\mathrm{eff}}>1000 , more than twice any value observed in MNIST \_ fc, suggesting high-dimensional margin sensitivity. These examples illustrate how Difficulty Profiles convert raw verifier outcomes into more actionable explanations, helping identify whether future progress should target tighter relaxations, better branching, dimension-aware heuristics, or other verifier improvements. 3. Difficulty Profiles help turn VeriStress-GT into a targeted stress-test suite. As VeriStress-GT instances scale, different constructors isolate different failure modes, making the benchmark useful not only for measuring performance but also for testing verifier improvements. For MEAP instances, increasing difficulty produces large relaxation gaps G_{\mathrm{IBP}} , high instability U , and large effective gradient dimensionality d_{\mathrm{eff}} . These instances therefore form a targeted stress test for methods that must reason about activation-pattern ambiguity, branching decisions, and loose intermediate bounds. In contrast, the Corners construction has A_{\tau}=0 and d_{\mathrm{eff}}\approx 0 , so it is structurally simple from an activation-pattern perspective. However, verifiers slow or timeout as G_{\mathrm{IBP}} grows, showing that relaxation looseness and geometric bound growth can be isolated from nonlinear-region complexity. These distinctions make the profiles actionable. A new branching heuristic can be evaluated on MEAP instances, a tighter relaxation can be tested on Corners instances, and depth-aware abstractions can be tested on Paired-Bias CNNs. Rather than treating all timeouts as equivalent failures, Difficulty Profiles reveal which instances are useful for stress-testing specific verifier capabilities. (a) Profile correlations (b) U\times d_{\mathrm{eff}} Figure 3: (left) Timeout AUC for each profile component across all benchmarks, treating timed-out instances as positives and solved instances as negatives; values above 0.5 indicate that larger component values are associated with timeouts. (right) Binned timeout rate over unstable fraction U and effective gradient dimension d_{\mathrm{eff}} , showing that timeouts can depend on interactions between profile components. For example, we see U have little effect on timeout rate when d_{\mathrm{eff}} is small. 5 Conclusion, Limitations, and Future Work We introduced VeriStress-GT, a modular framework for constructing neural network verification instances with verifier-independent ground-truth robustness labels. Together with the Difficulty Profile, VeriStress-GT enables targeted stress-testing and makes verifier timeouts more diagnosable. It also exposed numerical tolerance issues and implementation bugs, underscoring the need for ground-truth labels in reliable verifier evaluation. Several limitations and opportunities for future work remain. Due to computational costs, the verifiers were tested with a limited number of repeated seeds. Moreover, we do not claim that Difficulty Profiles are the sole source of predictive power for verifier runtime; instead, we aim for a collection of complementary, succinct, interpretable, and predictive components. Potential avenues for future work include extending the framework to additional architectures, such as residual networks and graph neural networks. Difficulty Profiles may also help guide and test verifiers for modern language-model components, where component-specific verifiers and compositional certificates could improve scalability. Acknowledgments This project has been supported by DARPA Artificial Intelligence Quantified (AIQ) grant HR00112520014. GM was partially supported by NSF grants DMS-2522495, DMS-2145630, CCF-2212520, DFG SPP 2298 “Theoretical Foundations of Deep Learning” project 464109215, and BMFTR in DAAD project 57616814 (SECAI). Appendix A Robust Constructor Details This appendix provides the implementation details for VeriStress-GT’s robust constructors described in Section 2 . A.1 Exact-Radius via MILP Let an L -layer ReLU MLP have preactivations s^{(\ell)}=W^{(\ell)}z^{(\ell-1)}+b^{(\ell)} and activations z^{(\ell)}=\sigma(s^{(\ell)}) , with z^{(0)}=x_{0}+\delta and \sigma(t)=\max\{t,0\} . Given valid preactivation bounds l_{j}^{(\ell)}\leq s_{j}^{(\ell)}\leq u_{j}^{(\ell)} obtained via simple interval arithmetic or Interval Bound Propagation [ 8 ] , each ReLU node is encoded using a binary variable a_{j}^{(\ell)}\in\{0,1\} and standard big- M constraints. The interval bounds are used only to define valid big- M constants and do not relax the network semantics. With binary decision variables, the constraints encode the ReLU graph exactly. For a fixed target class k\neq y , the minimum \ell_{\infty} perturbation required to make class k match or exceed the true-class logit is obtained by solving the following program: \displaystyle\min_{\delta,\,t,\,s,\,z,\,a}\quad \displaystyle t (smallest adversarial radius) s.t. \displaystyle-t\leq\delta_{i}\leq t,\quad\forall i ( \ell_{\infty} ball) \displaystyle z^{(0)}=x_{0}+\delta (perturbed input) \displaystyle s^{(\ell)}=W^{(\ell)}z^{(\ell-1)}+b^{(\ell)},\ \forall\ell (affine layers) \displaystyle z^{(\ell)}_{j}\geq 0,\quad z^{(\ell)}_{j}\geq s^{(\ell)}_{j} (ReLU lower bounds) \displaystyle z^{(\ell)}_{j}\leq u^{(\ell)}_{j}a^{(\ell)}_{j} (inactive case) \displaystyle z^{(\ell)}_{j}\leq s^{(\ell)}_{j}-l^{(\ell)}_{j}(1-a^{(\ell)}_{j}) (active case) \displaystyle a^{(\ell)}_{j}\in\{0,1\},\ \forall\ell,j (ReLU on/off) \displaystyle f_{k}(x_{0}+\delta)\geq f_{y}(x_{0}+\delta) \displaystyle\text{ (misclassification)}. The certified radius is r^{\star}=\min\limits_{k\neq y}t_{k}^{\star} . Thus, for any chosen \epsilon0 . Define b_{p,1}=\gamma_{p}-w_{p}^{\top}x_{0},\qquad b_{p,2}=\gamma_{p}+w_{p}^{\top}x_{0}. (16) Then, the paired preactivations satisfy z_{p,1}(x_{0})=z_{p,2}(x_{0})=\gamma_{p},\qquad b_{p,1}+b_{p,2}=2\gamma_{p}>0. (17) Thus both neurons are active at the nominal point, but the pair is constructed so that they cannot both be inactive at any input. To see this, observe that for any x , z_{p,1}(x)+z_{p,2}(x)=b_{p,1}+b_{p,2}=2\gamma_{p}. (18) Therefore, the two preactivations cannot both be negative. Moreover, \displaystyle r_{p}(x) \displaystyle=\max\{\sigma(z_{p,1}(x)),\sigma(z_{p,2}(x))\} (19) \displaystyle=\max\{0,z_{p,1}(x),z_{p,2}(x)\} \displaystyle\geq\frac{z_{p,1}(x)+z_{p,2}(x)}{2}=\gamma_{p}. Hence each pair contributes a global lower bound \gamma_{p} . Letting \gamma=\min\limits_{p\in[P]}\gamma_{p} , we have r_{p}(x)\geq\gamma for all p and all x . Since the target logit is f_{y}(x)=\min\limits_{p\in[P]}r_{p}(x) and all competing logits are fixed to zero, it follows that f_{y}(x)-f_{k}(x)\geq\gamma\qquad\forall x,\quad\forall k\neq y. (20) Thus the MEAP network is robust with margin at least \gamma on \mathcal{B}_{\epsilon}(x_{0}) . The construction is made difficult by choosing parameters so that both ReLU neurons in each pair are unstable over the perturbation box. For the \ell_{\infty} ball \mathcal{B}_{\epsilon}(x_{0}) , the minimum values of the two affine preactivations satisfy \min_{x\in\mathcal{B}_{\epsilon}(x_{0})}z_{p,1}(x)=\gamma_{p}-\epsilon\|w_{p}\|_{1},\qquad\min_{x\in\mathcal{B}_{\epsilon}(x_{0})}z_{p,2}(x)=\gamma_{p}-\epsilon\|w_{p}\|_{1}. (21) Similarly, both preactivations have maximum value \gamma_{p}+\epsilon\|w_{p}\|_{1} over the box. Therefore, if 0<\gamma_{p}<\epsilon\|w_{p}\|_{1}, (22) then the interval bounds for both z_{p,1} and z_{p,2} cross zero. Each ReLU is individually unstable, even though the pair satisfies the exact lower bound ( 19 ). This creates the intended verifier stress, as relaxations that treat the two ReLUs independently may admit the infeasible relaxed state \sigma(z_{p,1})=\sigma(z_{p,2})=0 , while the true network prevents it. Finally, the aggregation operations can be implemented using ReLU identities. For scalars a,b , note: \max\{a,b\}=b+\sigma(a-b),\qquad\min\{a,b\}=a-\sigma(a-b). (23) Thus the pairwise maxima r_{p}(x) and the final minimum over pairs can be represented as a standard piecewise-linear ReLU network. A.3 Input-Corner Stress Constructor Details We give the formal certificate for the input-corner construction. Let A\subseteq[d] be an active coordinate set with |A|=d_{act} , and let \mathcal{Q}_{\epsilon}(x_{0};A) denote the projection of \mathcal{B}_{\epsilon}(x_{0}) onto these active coordinates. Its vertices are: \mathcal{V}_{\epsilon}(x_{0};A)=\{(x_{0})_{A}+\epsilon s:s_{i}\in\{-1,+1\}\text{ for }i\in A,s_{i}=0\text{ for }i\notin A\}. (24) The constructed logits depend only on x_{A} . We set f_{y}(x)=0 and f_{k}(x)=h_{k}(x_{A})-\beta_{k} for k\neq y , where each h_{k}:\mathbb{R}^{d_{act}}\to\mathbb{R} is convex on \mathcal{Q}_{\epsilon}(x_{0};A) . For a desired margin \gamma>0 , define \beta_{k}=\max_{v\in\mathcal{V}_{\epsilon}(x_{0};A)}h_{k}(v)+\gamma. (25) Proposition 3 (Input-corner certificate) . If each h_{k} is convex on \mathcal{Q}_{\epsilon}(x_{0};A) and \beta_{k} is chosen as in ( 25 ), then the constructed classifier is robust on \mathcal{B}_{\epsilon}(x_{0}) with margin at least \gamma . Proof. For any x\in\mathcal{B}_{\epsilon}(x_{0}) , we have x_{A}\in\mathcal{Q}_{\epsilon}(x_{0};A) . Since \mathcal{Q}_{\epsilon}(x_{0};A) is a box, x_{A} can be written as a convex combination of its vertices: x_{A}=\sum_{v\in\mathcal{V}_{\epsilon}(x_{0};A)}\lambda_{v}v_{A},\qquad\lambda_{v}\geq 0,\qquad\sum_{v\in\mathcal{V}_{\epsilon}(x_{0};A)}\lambda_{v}=1 (26) And by the convexity of h_{k} . we have: h_{k}(x_{A})\leq\sum_{v\in\mathcal{V}_{\epsilon}(x_{0};A)}\lambda_{v}h_{k}(v_{A})\leq\max_{v\in\mathcal{V}_{\epsilon}(x_{0};A)}h_{k}(v_{A}). (27) Therefore, for any x\in\mathcal{B}_{\epsilon}(x_{0}) and k\neq y : \mu_{k}(x)=f_{y}(x)-f_{k}(x)=\beta_{k}-h_{k}(x_{A})\geq\beta_{k}-\max_{v\in\mathcal{V}_{\epsilon}(x_{0};A)}h_{k}(v)=\gamma. (28) Since this holds for every k\neq y , we have \mu(x)=\min\limits_{k\neq y}\mu_{k}(x)\geq\gamma throughout \mathcal{B}_{\epsilon}(x_{0}) . ∎ A ReLU implementation is obtained by choosing h_{k}(u)=\sum_{j=1}^{J}c_{k,j}\sigma(a_{j}^{\top}u+b_{j}),\qquad c_{k,j}\geq 0 (29) Because u\mapsto\sigma(a_{j}^{\top}u+b_{j}) is convex and nonnegative linear combinations preserve convexity, each h_{k} is convex. To make the instance difficult, the constructor may place hinges near the nominal input by setting, for example, b_{j}=-a_{j}^{\top}(x_{0})_{A} . Then the j -th hinge preactivation is zero at x_{0} , and its interval over the active-coordinate box satisfies the following: a_{j}^{\top}(u-(x_{0})_{A})\in[-\epsilon\|a_{j}\|_{1},\epsilon\|a_{j}\|_{1}], (30) so the corresponding ReLU is unstable under IBP bounds. Increasing the number of hinges J , the active dimension d_{\mathrm{act}} , or the hinge scales \|a_{j}\|_{1} increases the number and magnitude of unstable hinge contributions while preserving the robustness certificate. A.4 Contractive CNN Constructor Details We give the formal certificate for the deep contractive CNN constructor. Write the convolutional feature extractor as \Phi=C_{D}\circ C_{D-1}\circ\cdots\circ C_{1}\circ P where P is an optional front-end map and C_{1},\dots,C_{D} are contractive convolutional blocks. Let L_{\mathrm{front}} denote the induced \ell_{\infty} Lipschitz constant of P , with L_{\mathrm{front}}=1 if no front-end map is used. Assume each block C_{\ell} is \ell_{\infty} -Lipschitz with constant at most \lambda<1 . Then, for all x,x^{\prime} , \|\Phi(x)-\Phi(x^{\prime})\|_{\infty}\leq L_{\mathrm{front}}\lambda^{D}\|x-x^{\prime}\|_{\infty}. (31) This follows directly by composing the Lipschitz constants of P,C_{1},\dots,C_{D} . Next, define the centered target logit by f_{y}(x)=\Gamma+w_{y}^{\top}(\Phi(x)-\Phi(x_{0})) and set f_{k}(x)=0\;\forall k\neq y . The following Proposition defines our robustness claim for the constructor: Proposition 4 (Contractive CNN certificate) . If \Gamma>\|w_{y}\|_{1}L_{\mathrm{front}}\lambda^{D}\epsilon, (32) then the classifier \Phi is robust on \mathcal{B}_{\epsilon}(x_{0}) . Proof. For any x=x_{0}+\delta with \|\delta\|_{\infty}\leq\epsilon , Hölder’s inequality and ( 31 ) give \displaystyle\left|w_{y}^{\top}(\Phi(x)-\Phi(x_{0}))\right| \displaystyle\leq\|w_{y}\|_{1}\|\Phi(x)-\Phi(x_{0})\|_{\infty} (33) \displaystyle\leq\|w_{y}\|_{1}L_{\mathrm{front}}\lambda^{D}\|x-x_{0}\|_{\infty} \displaystyle\leq\|w_{y}\|_{1}L_{\mathrm{front}}\lambda^{D}\epsilon. Therefore, f_{y}(x)\geq\Gamma-\|w_{y}\|_{1}L_{\mathrm{front}}\lambda^{D}\epsilon>0=f_{k}(x)\qquad\forall k\neq y. (34) Thus, \mu(x)=\min_{k\neq y}(f_{y}(x)-f_{k}(x))>0 throughout \mathcal{B}_{\epsilon}(x_{0}) , so the instance is robust. ∎ The centered logit is convenient because the nominal target logit is exactly \Gamma and all competing logits are fixed to zero. An un-centered linear logit head can also be used. Suppose f_{i}(x)=b_{i}+w_{i}^{\top}\Phi(x),\qquad i\in[c]. (35) Then for each k\neq y , define the nominal class-wise margin \mu_{k}(x_{0})=f_{y}(x_{0})-f_{k}(x_{0}) . Then, \mu_{k}(x)=\mu_{k}(x_{0})+(w_{y}-w_{k})^{\top}(\Phi(x)-\Phi(x_{0})) . Therefore, by the same Lipschitz argument: \mu_{k}(x)\geq\mu_{k}(x_{0})-\|w_{y}-w_{k}\|_{1}L_{\mathrm{front}}\lambda^{D}\epsilon. (36) Thus, the uncentered head is robust whenever \mu_{k}(x_{0})>\|w_{y}-w_{k}\|_{1}L_{\mathrm{front}}\lambda^{D}\epsilon\qquad\text{for all }k\neq y. (37) A.5 Paired-Bias CNN Constructor Details We give the formal certificate and instability parameterization for the paired-bias CNN constructor. Let Z=\Psi(x) denote the feature map produced by any upstream convolutional layers. For each pair i\in[P] , the two channels share the same convolutional filter \mathcal{W}_{i} and differ only in their biases. Write s^{(i)}=\mathcal{W}_{i}\star Z\in\mathbb{R}^{H_{\mathrm{sp}}\times W_{\mathrm{sp}}} so that at spatial location (h,w) , the paired activations are \sigma(s_{h,w}^{(i)}+b_{i}) and \sigma(s_{h,w}^{(i)}+c_{i}) , where b_{i}>c_{i} . The certificate follows from monotonicity of the ReLU function. For any s\in\mathbb{R} and any b_{i}>c_{i} , we have s+b_{i}>s+c_{i} , and since \sigma is monotone and nondecreasing, then: \sigma(s+b_{i})\geq\sigma(s+c_{i}). (38) Therefore, each paired difference is nonnegative: \sigma(s+b_{i})-\sigma(s+c_{i})\geq 0\qquad\forall s\in\mathbb{R}. (39) Next, define the logit outputs as the following: f_{y}(x)=\Gamma+\frac{1}{PH_{\mathrm{sp}}W_{\mathrm{sp}}}\sum_{i=1}^{P}\sum_{h=1}^{H_{\mathrm{sp}}}\sum_{w=1}^{W_{\mathrm{sp}}}\left[\sigma(s_{h,w}^{(i)}+b_{i})-\sigma(s_{h,w}^{(i)}+c_{i})\right],\qquad f_{k}(x)=0\quad\text{for all }k\neq y. (40) Proposition 5 (Paired-bias CNN certificate) . If \Gamma>0 and b_{i}>c_{i} for every pair i\in[P] , then the classifier defined in ( 40 ) is robust with margin at least \Gamma for every input x . Proof. By ( 39 ), every summand in ( 40 ) is nonnegative. Hence f_{y}(x)\geq\Gamma for every input x . Since f_{k}(x)=0 for all k\neq y , we have f_{y}(x)-f_{k}(x)\geq\Gamma>0 for every x and every k\neq y . Therefore \mu(x)=\min_{k\neq y}(f_{y}(x)-f_{k}(x))\geq\Gamma, so the classifier is robust on any perturbation set \mathcal{B}_{\epsilon}(x_{0}) . ∎ To make the instance difficult for relaxation-based verifiers, the constructor chooses biases so that many paired ReLUs are unstable over the perturbation set. Suppose interval propagation gives bounds s_{h,w}^{(i)}\in[s_{\mathrm{lo},h,w}^{(i)},s_{\mathrm{hi},h,w}^{(i)}] for the shared convolutional response over \mathcal{B}_{\epsilon}(x_{0}) . In practice, we choose a channelwise center t_{i} , such as a spatial average of interval midpoints, and a bias half-gap \Delta_{i}>0 , and set b_{i}=-t_{i}+\Delta_{i},\qquad c_{i}=-t_{i}-\Delta_{i}. (41) Then b_{i}-c_{i}=2\Delta_{i}>0 , so the monotonicity certificate remains valid. For a given spatial location (h,w) , the shifted intervals are s_{h,w}^{(i)}+b_{i}\in[s_{\mathrm{lo},h,w}^{(i)}-t_{i}+\Delta_{i},\;s_{\mathrm{hi},h,w}^{(i)}-t_{i}+\Delta_{i}], (42) and s_{h,w}^{(i)}+c_{i}\in[s_{\mathrm{lo},h,w}^{(i)}-t_{i}-\Delta_{i},\;s_{\mathrm{hi},h,w}^{(i)}-t_{i}-\Delta_{i}]. (43) When these intervals cross zero, the corresponding ReLUs are unstable under interval bounds. Therefore, the constructor can create many unstable paired activations while preserving the exact nonnegativity guarantee. Independent relaxations may lose the fact that the two ReLUs are functions of the same scalar s_{h,w}^{(i)} , and can therefore produce a negative lower bound on a quantity that is globally nonnegative. A.6 Fixed-Ordering Softmax Attention Constructor Details The robustness certificate for the fixed-ordering attention constructor has two parts. First, we show that the nominal row-wise score maximizers remain unchanged throughout the perturbation set. This ensures that the attention score pattern is stable. Second, we bound the total change in the attention module (i.e. score matrix times the value matrix XW_{V} ) output. This bound, combined with a Lipschitz downstream head and a sufficiently large nominal classification margin, gives the final robustness certificate. Thus, the first proposition certifies score-pattern stability, while the second proposition certifies classification robustness. Let X=X_{0}+\Delta X , and write \delta^{(i)} for the i -th row of \Delta X . We assume \|\Delta X\|_{\infty}\leq\epsilon , so \|\delta^{(i)}\|_{2}\leq\epsilon\sqrt{d_{\mathrm{tok}}} for every i . Part 1: Score-gap stability. For any j\neq\pi_{i}^{\star} , since X=X_{0}+\Delta X , we have \displaystyle S_{i,\pi_{i}^{\star}}(X)-S_{ij}(X) \displaystyle=(x_{0}^{(i)}+\delta^{(i)})^{\top}M\left[(x_{0}^{(\pi_{i}^{\star})}+\delta^{(\pi_{i}^{\star})})-(x_{0}^{(j)}+\delta^{(j)})\right] \displaystyle={x_{0}^{(i)}}^{\top}M\left(x_{0}^{(\pi_{i}^{\star})}-x_{0}^{(j)}\right)+{\delta^{(i)}}^{\top}M\left(x_{0}^{(\pi_{i}^{\star})}-x_{0}^{(j)}\right) \displaystyle\qquad+{x_{0}^{(i)}}^{\top}M\left(\delta^{(\pi_{i}^{\star})}-\delta^{(j)}\right)+{\delta^{(i)}}^{\top}M\left(\delta^{(\pi_{i}^{\star})}-\delta^{(j)}\right). (44) The first term is the nominal score gap, {x_{0}^{(i)}}^{\top}M\left(x_{0}^{(\pi_{i}^{\star})}-x_{0}^{(j)}\right)=S_{i,\pi_{i}^{\star}}(X_{0})-S_{ij}(X_{0})=\Delta_{ij}. Therefore, \displaystyle\left[S_{i,\pi_{i}^{\star}}(X)-S_{ij}(X)\right]-\Delta_{ij} \displaystyle\qquad={\delta^{(i)}}^{\top}M\left(x_{0}^{(\pi_{i}^{\star})}-x_{0}^{(j)}\right)+{x_{0}^{(i)}}^{\top}M\left(\delta^{(\pi_{i}^{\star})}-\delta^{(j)}\right)+{\delta^{(i)}}^{\top}M\left(\delta^{(\pi_{i}^{\star})}-\delta^{(j)}\right). (45) Using |u^{\top}Mv|\leq\|M\|_{\mathrm{op}}\|u\|_{2}\|v\|_{2} , \|\delta^{(i)}\|_{2}\leq\epsilon\sqrt{d_{\mathrm{tok}}} , and \|\delta^{(\pi_{i}^{\star})}-\delta^{(j)}\|_{2}\leq 2\epsilon\sqrt{d_{\mathrm{tok}}} , we obtain \left|\left[S_{i,\pi_{i}^{\star}}(X)-S_{ij}(X)\right]-\Delta_{ij}\right|\leq\epsilon C_{ij}(\epsilon), (46) where C_{ij}(\epsilon)=\sqrt{d_{\mathrm{tok}}}\,\|M\|_{\mathrm{op}}\left(\|x_{0}^{(\pi_{i}^{\star})}-x_{0}^{(j)}\|_{2}+2\|x_{0}^{(i)}\|_{2}\right)+2\epsilon d_{\mathrm{tok}}\,\|M\|_{\mathrm{op}}. (47) Proposition 6 (Attention score-pattern stability) . If \Delta_{ij}>\epsilon C_{ij}(\epsilon) for every i and every j\neq\pi_{i}^{\star} , then \pi(X)=\pi^{\star} for every X satisfying \|X-X_{0}\|_{\infty}\leq\epsilon . Proof. By ( 46 ), S_{i,\pi_{i}^{\star}}(X)-S_{ij}(X)\geq\Delta_{ij}-\epsilon C_{ij}(\epsilon)>0 (48) for every j\neq\pi_{i}^{\star} . Hence the row-wise maximizer remains \pi_{i}^{\star} for every row i . ∎ Part 2: Attention-output perturbation. We next bound the attention output. Let A_{0}=A(X_{0}) , \widetilde{A}=A(X) , V_{0}=X_{0}W_{V} , and \Delta V=\Delta XW_{V} . The exact decomposition is \mathrm{Attn}(X)-\mathrm{Attn}(X_{0})=(\widetilde{A}-A_{0})V_{0}+A_{0}\Delta V+(\widetilde{A}-A_{0})\Delta V. (49) For every score entry, bilinearity gives: |S_{ij}(X)-S_{ij}(X_{0})|\leq\epsilon\sqrt{d_{\mathrm{tok}}}\,\|M\|_{\mathrm{op}}\left(\|x_{0}^{(i)}\|_{2}+\|x_{0}^{(j)}\|_{2}\right)+\epsilon^{2}d_{\mathrm{tok}}\,\|M\|_{\mathrm{op}}. (50) Define \bar{B}_{S}(\epsilon)=\max_{i,j}\left[\sqrt{d_{\mathrm{tok}}}\,\|M\|_{\mathrm{op}}\left(\|x_{0}^{(i)}\|_{2}+\|x_{0}^{(j)}\|_{2}\right)+\epsilon d_{\mathrm{tok}}\,\|M\|_{\mathrm{op}}\right]. (51) Then \|S(X)-S(X_{0})\|_{\infty}\leq\epsilon\bar{B}_{S}(\epsilon) . Using the softmax Jacobian bound \|\nabla\mathrm{softmax}(z)\|_{\mathrm{op}}\leq\frac{1}{2} , for each attention row i we have \|\widetilde{a}_{i}-a_{i}^{0}\|_{1}\leq\frac{n}{2}\epsilon\bar{B}_{S}(\epsilon). (52) Also, \|\Delta V\|_{2,\infty}\leq\epsilon\sqrt{d_{\mathrm{tok}}}\,\|W_{V}\|_{\mathrm{op}} , where \|Z\|_{2,\infty}=\max_{i}\|Z[i,:]\|_{2} . Applying these bounds to the three terms in ( 49 ) results in: \|\mathrm{Attn}(X)-\mathrm{Attn}(X_{0})\|_{2,\infty}\leq\epsilon L_{\mathrm{attn}}(\epsilon), (53) where L_{\mathrm{attn}}(\epsilon)=\frac{n}{2}\bar{B}_{S}(\epsilon)\|V_{0}\|_{2,\infty}+\sqrt{d_{\mathrm{tok}}}\,\|W_{V}\|_{\mathrm{op}}+\frac{n}{2}\epsilon\bar{B}_{S}(\epsilon)\sqrt{d_{\mathrm{tok}}}\,\|W_{V}\|_{\mathrm{op}}. (54) Since \|Z\|_{F}\leq\sqrt{n}\|Z\|_{2,\infty} , this implies \|\mathrm{Attn}(X)-\mathrm{Attn}(X_{0})\|_{F}\leq\sqrt{n}L_{\mathrm{attn}}(\epsilon)\epsilon. (55) Proposition 7 (Fixed-pattern attention robustness) . Let f=h\circ\mathrm{Attn} , and suppose each logit of h is L_{h} -Lipschitz with respect to the Frobenius norm. If the score-pattern stability condition holds and \mu(X_{0})>2L_{h}\sqrt{n}L_{\mathrm{attn}}(\epsilon)\epsilon , then f is robust on \mathcal{B}_{\epsilon}(X_{0}) . Proof. By ( 55 ) and the logit-wise L_{h} -Lipschitzness of h , for each class r , |f_{r}(X)-f_{r}(X_{0})|\leq L_{h}\sqrt{n}L_{\mathrm{attn}}(\epsilon)\epsilon. (56) Therefore, for any k\neq y , \displaystyle f_{y}(X)-f_{k}(X) \displaystyle\geq f_{y}(X_{0})-f_{k}(X_{0})-|f_{y}(X)-f_{y}(X_{0})|-|f_{k}(X)-f_{k}(X_{0})| (57) \displaystyle\geq\mu(X_{0})-2L_{h}\sqrt{n}L_{\mathrm{attn}}(\epsilon)\epsilon>0. Thus the predicted class remains y for every X\in\mathcal{B}_{\epsilon}(X_{0}) . ∎ A.7 Dominant-Key Linear Attention Constructor Details The robustness certificate has three steps, and we use the same notation as in the main text. First, we show that the dominance condition implies that each attention row is close to the value vector associated with its dominant key. Second, we show that this closeness gives a uniform bound on the full attention-output drift. Third, this output-drift bound combines with the nominal classification margin to certify robustness. Part 1: Closeness to dominant value. The dominance condition says that for query row i , the unnormalized weight assigned to key j_{i}^{\star} is at least \rho_{i} times the total weight assigned to all other keys. The next lemma makes the consequence precise: Lemma 8 (Closeness to the dominant value) . If row i satisfies the dominance condition in ( 7 ) throughout \mathcal{B}_{\epsilon}(X_{0}) , then for every X\in\mathcal{B}_{\epsilon}(X_{0}) , \left\|\mathrm{Attn}_{\mathrm{lin}}(X)[i,:]-V(X)[j_{i}^{\star},:]\right\|_{2}\leq\frac{1}{1+\rho_{i}}\max_{j\neq j_{i}^{\star}}\left\|V(X)[j,:]-V(X)[j_{i}^{\star},:]\right\|_{2}. (58) Proof. Let S_{i}(X)=\sum\limits_{j\neq j_{i}^{\star}}w_{ij}(X) and w_{i}^{\star}(X)=w_{ij_{i}^{\star}}(X) . We also have that w_{i}^{\star}(X)\geq\rho_{i}S_{i}(X) by ( 7 ). Therefore: \alpha_{ij_{i}^{\star}}(X)=\frac{w_{i}^{\star}(X)}{w_{i}^{\star}(X)+S_{i}(X)}\geq\frac{\rho_{i}}{1+\rho_{i}},\qquad 1-\alpha_{ij_{i}^{\star}}(X)\leq\frac{1}{1+\rho_{i}}. (59) Using the definition of linear attention, \mathrm{Attn}_{\mathrm{lin}}(X)[i,:]-V(X)[j_{i}^{\star},:]=\sum_{j\neq j_{i}^{\star}}\alpha_{ij}(X)\left(V(X)[j,:]-V(X)[j_{i}^{\star},:]\right). (60) Applying the triangle inequality and ( 59 ) gives \displaystyle\left\|\mathrm{Attn}_{\mathrm{lin}}(X)[i,:]-V(X)[j_{i}^{\star},:]\right\|_{2} \displaystyle\leq\sum_{j\neq j_{i}^{\star}}\alpha_{ij}(X)\left\|V(X)[j,:]-V(X)[j_{i}^{\star},:]\right\|_{2} (61) \displaystyle\leq\left(1-\alpha_{ij_{i}^{\star}}(X)\right)\max_{j\neq j_{i}^{\star}}\left\|V(X)[j,:]-V(X)[j_{i}^{\star},:]\right\|_{2} \displaystyle\leq\frac{1}{1+\rho_{i}}\max_{j\neq j_{i}^{\star}}\left\|V(X)[j,:]-V(X)[j_{i}^{\star},:]\right\|_{2}. ∎ Part 2: Attention-output perturbation. The previous lemma controls each attention row relative to its dominant value vector. We now compare the full attention outputs at X and X_{0} by inserting the dominant value vector at both inputs. For compactness, let V_{0}=V(X_{0}) and set L_{V}=\sqrt{d_{\mathrm{tok}}}\|W_{V}\|_{\mathrm{op}} . If X=X_{0}+\Delta X and \|\Delta X\|_{\infty}\leq\epsilon , then each token perturbation satisfies \|\delta^{(i)}\|_{2}\leq\epsilon\sqrt{d_{\mathrm{tok}}} , so \|V(X)[j,:]-V_{0}[j,:]\|_{2}=\|\delta^{(j)}W_{V}\|_{2}\leq\epsilon L_{V}. (62) Proposition 9 (Dominant-key attention-output perturbation) . Suppose every row satisfies the dominance condition in ( 7 ) throughout \mathcal{B}_{\epsilon}(X_{0}) , and let \rho=\min\limits_{i}\rho_{i} . Then for every X\in\mathcal{B}_{\epsilon}(X_{0}) , \|\mathrm{Attn}_{\mathrm{lin}}(X)-\mathrm{Attn}_{\mathrm{lin}}(X_{0})\|_{2,\infty}\leq\frac{2}{1+\rho}D_{V}(X_{0})+\left(1+\frac{2}{1+\rho}\right)\epsilon L_{V}. (63) Proof. Fix a row i . Insert the value vector associated with the dominant key at both X and X_{0} : \displaystyle\left\|\mathrm{Attn}_{\mathrm{lin}}(X)[i,:]-\mathrm{Attn}_{\mathrm{lin}}(X_{0})[i,:]\right\|_{2} (64) \displaystyle\leq\left\|\mathrm{Attn}_{\mathrm{lin}}(X)[i,:]-V(X)[j_{i}^{\star},:]\right\|_{2}+\left\|V(X)[j_{i}^{\star},:]-V_{0}[j_{i}^{\star},:]\right\|_{2} \displaystyle+\left\|V_{0}[j_{i}^{\star},:]-\mathrm{Attn}_{\mathrm{lin}}(X_{0})[i,:]\right\|_{2}. By Lemma 8 applied at X , \left\|\mathrm{Attn}_{\mathrm{lin}}(X)[i,:]-V(X)[j_{i}^{\star},:]\right\|_{2}\leq\frac{1}{1+\rho}\max_{j\neq j_{i}^{\star}}\|V(X)[j,:]-V(X)[j_{i}^{\star},:]\|_{2}. (65) For every j\neq j_{i}^{\star} , adding and subtracting nominal values gives \displaystyle\|V(X)[j,:]-V(X)[j_{i}^{\star},:]\|_{2} \displaystyle\leq\|V_{0}[j,:]-V_{0}[j_{i}^{\star},:]\|_{2} (66) \displaystyle+\|V(X)[j,:]-V_{0}[j,:]\|_{2}+\|V(X)[j_{i}^{\star},:]-V_{0}[j_{i}^{\star},:]\|_{2} \displaystyle\leq D_{V}(X_{0})+2\epsilon L_{V}. Thus the first term in ( 64 ) is bounded by \frac{D_{V}(X_{0})+2\epsilon L_{V}}{(1+\rho)} . The middle term is bounded by \epsilon L_{V} using ( 62 ). The last term is bounded by \frac{D_{V}(X_{0})}{(1+\rho)} by Lemma 8 applied at X_{0} . Summing the three bounds gives \left\|\mathrm{Attn}_{\mathrm{lin}}(X)[i,:]-\mathrm{Attn}_{\mathrm{lin}}(X_{0})[i,:]\right\|_{2}\leq\frac{2}{1+\rho}D_{V}(X_{0})+\left(1+\frac{2}{1+\rho}\right)\epsilon L_{V}. (67) Taking the maximum over rows gives the \|\cdot\|_{2,\infty} bound. ∎ Part 3: Robustness from output drift. The previous proposition bounds the drift of the linear-attention output. The final step is the same argument used in the fixed-ordering softmax constructor proof, i.e. if the downstream head cannot move the logits enough to close the nominal margin, then the predicted class is fixed. Proposition 10 (Dominant-key linear attention robustness certificate) . Let f=h\circ\mathrm{Attn}_{\mathrm{lin}} , and suppose each logit of h is L_{h} -Lipschitz with respect to the Frobenius norm. Define \Delta_{\mathrm{lin}}=\frac{2}{1+\rho}D_{V}(X_{0})+\left(1+\frac{2}{1+\rho}\right)\epsilon L_{V}. (68) If \mu(X_{0})>2L_{h}\sqrt{n}\,\Delta_{\mathrm{lin}} , then f is robust on \mathcal{B}_{\epsilon}(X_{0}) . Proof. By Proposition 9 , \|\mathrm{Attn}_{\mathrm{lin}}(X)-\mathrm{Attn}_{\mathrm{lin}}(X_{0})\|_{2,\infty}\leq\Delta_{\mathrm{lin}} . Therefore, \|\mathrm{Attn}_{\mathrm{lin}}(X)-\mathrm{Attn}_{\mathrm{lin}}(X_{0})\|_{F}\leq\sqrt{n}\,\Delta_{\mathrm{lin}}. (69) Since each logit of h is L_{h} -Lipschitz, for every class r , |f_{r}(X)-f_{r}(X_{0})|\leq L_{h}\sqrt{n}\,\Delta_{\mathrm{lin}}. (70) Therefore, for any k\neq y , \displaystyle f_{y}(X)-f_{k}(X) \displaystyle\geq f_{y}(X_{0})-f_{k}(X_{0})-|f_{y}(X)-f_{y}(X_{0})|-|f_{k}(X)-f_{k}(X_{0})| (71) \displaystyle\geq\mu(X_{0})-2L_{h}\sqrt{n}\,\Delta_{\mathrm{lin}}>0. Thus the predicted class remains y for every X\in\mathcal{B}_{\epsilon}(X_{0}) . ∎ A.8 Polynomial Network Constructor Construction and robustness certificate We describe the polynomial network constructor in more detail. The construction applies to binary classifiers whose margin is a polynomial function of the input. Let f:\mathbb{R}^{n}\to\mathbb{R}^{2} be a binary classifier, and write \mu(x)=f_{1}(x)-f_{2}(x) for its margin polynomial. The decision boundary is the real algebraic hypersurface D=\{x\in\mathbb{R}^{n}:\mu(x)=0\} . A point x_{0} is robust at radius \epsilon with respect to a norm \|\cdot\| if \mu has constant sign on B_{\epsilon}(x_{0})=\{x:\|x-x_{0}\|\leq\epsilon\} . Equivalently, B_{\epsilon}(x_{0})\cap D=\emptyset . The constructor proceeds in three steps. First, it samples a smooth point p\in D , so that \nabla\mu(p)\neq 0 . Second, it chooses a norm-adapted normal direction u(p) pointing to one side of the decision boundary. More precisely, u(p) is normalized in the chosen norm and satisfies \nabla\mu(p)\cdot u(p)>0 . Third, for a target verification radius \epsilon>0 and buffer \delta>0 , it sets x_{0}=p+(\epsilon+\delta)u(p) . The sampled point p is then a known boundary point at distance \epsilon+\delta from x_{0} , and hence lies just outside the perturbation set B_{\epsilon}(x_{0}) . The preceding step is only a local construction. It guarantees that one known point of the decision boundary lies outside the verification set, but it does not rule out the possibility that another branch or component of D enters B_{\epsilon}(x_{0}) . The robustness label is therefore obtained from the following global separation certificate. Proposition 11 . If B_{\epsilon}(x_{0})\cap D=\emptyset , then x_{0} is robust at radius \epsilon . Proof. Since B_{\epsilon}(x_{0}) is connected and \mu is continuous, the image \mu(B_{\epsilon}(x_{0})) is connected in \mathbb{R} . If B_{\epsilon}(x_{0})\cap D=\emptyset , then \mu(x)\neq 0 for every x\in B_{\epsilon}(x_{0}) . Hence \mu cannot change sign on B_{\epsilon}(x_{0}) . Therefore the classifier assigns the same label to every point in B_{\epsilon}(x_{0}) , so x_{0} is robust at radius \epsilon . ∎ Thus the constructor separates the task of generating near-boundary candidates from the task of certifying their ground-truth labels. The perturbation step places x_{0} close to the algebraic decision boundary with a prescribed buffer \delta , while the global separation check certifies that the full perturbation set remains on one side of D . Decreasing \delta produces instances that are robust but closer to failure, and therefore harder for verifiers to certify. Boundary sampling and shallow polynomial networks We now describe how boundary points are sampled and how the construction is instantiated for the shallow polynomial networks used in the experiments. Since \mu is a polynomial, points on D=\{\mu=0\} can be obtained by slicing D with affine linear spaces. In our setting D is a hypersurface, so a generic affine line is enough. We choose a random point a\in\mathbb{R}^{n} and a random direction v\in\mathbb{R}^{n} , and restrict \mu to the line \ell(t)=a+tv . This gives the univariate polynomial \mu_{\ell}(t)=\mu(a+tv) . Each real root of \mu_{\ell} gives a boundary point p=\ell(t)\in D . For a generic line, the intersection is transverse away from the singular locus of D , so sampled points are smooth unless they also satisfy \nabla\mu(p)=0 . We discard such points. In the experiments, we use one-hidden-layer polynomial networks with architecture (n,h,2) , f(x)=W_{2}(W_{1}x+b_{1})^{d}+b_{2}, where the power is applied entrywise, W_{1}\in\mathbb{R}^{h\times n} , b_{1}\in\mathbb{R}^{h} , W_{2}\in\mathbb{R}^{2\times h} , and b_{2}\in\mathbb{R}^{2} . Writing W_{2,1} and W_{2,2} for the two rows of W_{2} , the margin polynomial is \mu(x)=(W_{2,1}-W_{2,2})\cdot(W_{1}x+b_{1})^{d}+(b_{2,1}-b_{2,2}). Thus the decision boundary D=\{\mu=0\} is a real algebraic hypersurface of degree at most d . For the \ell_{\infty} perturbation sets used in our experiments, we take the norm-adapted normal direction to be u(p)=\operatorname{sign}(\nabla\mu(p)) . This direction has \|u(p)\|_{\infty}=1 and satisfies \nabla\mu(p)\cdot u(p)=\|\nabla\mu(p)\|_{1}>0 at every smooth boundary point. We fix a push distance r>0 , set x_{0}=p+ru(p) , and verify at radius \epsilon=r-\delta . Equivalently, r=\epsilon+\delta . The sampled boundary point p is then at \ell_{\infty} distance r from x_{0} , while the verification box B_{\epsilon}(x_{0}) has buffer \delta from this known boundary point. Numerical separation check and verifier protocol The global condition B_{\epsilon}(x_{0})\cap D=\emptyset is the mathematical certificate for robustness. In the present experiments, we implement this check numerically before passing instances to the verifier. For each candidate center x_{0} , we search for an intersection between the verification box and the decision boundary by solving \min_{z\in B_{\epsilon}(x_{0})}\mu(z)^{2}. The minimum is zero if and only if the box intersects D=\{\mu=0\} . We solve this box-constrained problem using L-BFGS-B from 50 random initializations in B_{\epsilon}(x_{0}) , with a maximum of 500 iterations per restart. If the smallest value found is below 10^{-6} , we treat the candidate as numerically intersecting the decision boundary and discard it. Otherwise, we keep the candidate as passing the numerical separation check. For each retained instance, we export the network to ONNX and generate a VNNLIB specification for the \ell_{\infty} box B_{\epsilon}(x_{0}) . The input constraints are x_{0,i}-\epsilon\leq x_{i}\leq x_{0,i}+\epsilon for i=1,\ldots,n . The output constraint requires the predicted label at x_{0} to remain unchanged throughout the box. Equivalently, if \mu(x_{0})>0 , the verifier is asked to prove \mu(x)>0 for all x\in B_{\epsilon}(x_{0}) , and if \mu(x_{0})<0 , it is asked to prove \mu(x)<0 for all x\in B_{\epsilon}(x_{0}) . We record verifier outcomes as robust , non-robust , timeout , or unknown . A robust result means that the verifier certified the output constraint over the full box. A non-robust result means that it found a violation of the specification. A timeout or unknown result means that no certificate or counterexample was found within the time limit. Ablation Study Results Table 1 summarizes an ablation study for the shallow polynomial network constructor using \alpha,\beta -CROWN. We vary one parameter at a time around a baseline configuration, keeping the push distance fixed at r=0.02 and setting the verification radius to \epsilon=r-\delta . Each row reports the number of retained instances submitted to \alpha,\beta -CROWN after the numerical separation check in Section A.8 . A timeout is recorded when \alpha,\beta -CROWN does not return either a certificate or a counterexample within the time limit in the Limit column. The clearest transitions in this ablation occur when increasing the polynomial degree d or decreasing the buffer \delta . This matches the geometry of the construction: d controls the degree of the margin polynomial, and hence the algebraic complexity of the decision boundary. This is also consistent with the ED degree formulas in [ 1 ] , which count complex critical points of the closest-boundary equations and involve powers of d-1 . The buffer \delta controls a complementary geometric difficulty: since \epsilon=r-\delta , smaller \delta places the verification box closer to the sampled boundary point, leaving less separation for \alpha,\beta -CROWN to certify. In contrast, varying n or h changes the ambient dimension or the number of hidden units, but has a milder effect in this sweep. Table 1: Verification outcomes for retained near-boundary instances generated from shallow polynomial networks and evaluated with \alpha,\beta -CROWN. The push distance is fixed at r=0.02 , and the verification radius is \epsilon=r-\delta . Mean time includes timeout runs; mean time without timeouts averages only certified runs. n d h \delta Limit Points Robust Timeouts Mean time Mean time (no T/O) 50 10 100 5\cdot 10^{-3} 300s 5 5 0 9.10s 9.10s 100 10 100 5\cdot 10^{-3} 300s 5 5 0 7.88s 7.88s 200 10 100 5\cdot 10^{-3} 300s 5 5 0 7.86s 7.86s 300 10 100 5\cdot 10^{-3} 300s 5 5 0 8.42s 8.42s 100 2 100 5\cdot 10^{-3} 300s 5 5 0 8.32s 8.32s 100 4 100 5\cdot 10^{-3} 300s 5 5 0 8.63s 8.63s 100 6 100 5\cdot 10^{-3} 300s 5 5 0 8.36s 8.36s 100 8 100 5\cdot 10^{-3} 300s 5 5 0 8.22s 8.22s 100 10 100 5\cdot 10^{-3} 300s 5 5 0 7.88s 7.88s 100 12 100 5\cdot 10^{-3} 300s 5 5 0 8.23s 8.23s 100 14 100 5\cdot 10^{-3} 300s 5 5 0 8.22s 8.22s 100 16 100 5\cdot 10^{-3} 300s 5 5 0 8.00s 8.00s 100 18 100 5\cdot 10^{-3} 300s 5 4 1 68.43s 8.53s 100 20 100 5\cdot 10^{-3} 300s 5 3 2 129.13s 9.50s 100 22 100 5\cdot 10^{-3} 300s 5 2 3 187.51s 8.85s 100 10 50 5\cdot 10^{-3} 300s 5 5 0 6.28s 6.28s 100 10 100 5\cdot 10^{-3} 300s 5 5 0 7.88s 7.88s 100 10 200 5\cdot 10^{-3} 300s 5 5 0 6.22s 6.22s 100 10 300 5\cdot 10^{-3} 300s 5 5 0 6.12s 6.12s 100 10 500 5\cdot 10^{-3} 300s 5 5 0 6.77s 6.77s 100 10 100 10^{-3} 300s 5 4 1 66.72s 6.58s 100 10 100 5\cdot 10^{-3} 300s 5 5 0 7.88s 7.88s 100 10 100 10^{-4} 300s 5 1 4 248.96s 7.94s Table 2 reports a complementary verifier-comparison experiment on selected polynomial-network instances from the VeriStress study. Unlike Table 1 , this table is not an ablation study for \alpha,\beta -CROWN over the full parameter sweep. Instead, each row records the outcome of running several verifiers on a retained near-boundary instance generated by the same constructor. The purpose is to show that the construction produces instances that can stress multiple verification back ends. Across these selected instances, \alpha,\beta -CROWN certifies many cases but begins to time out as d increases or \delta decreases, while NeuralSAT and PyRAT time out on more of the listed configurations. Table 2: Verifier outcomes for selected retained near-boundary instances used in the VeriStress study described in Section 4 . The push distance is fixed at r=0.02 , the verification radius is \epsilon=r-\delta , and the timeout is 360 seconds. Entries report certification time when the verifier certifies robustness and “Timeout” otherwise. Marabou and nnenum returned errors on these instances and are omitted. n d h \delta \alpha,\beta -CROWN outcome NeuralSAT outcome PyRAT outcome 50 10 100 5\cdot 10^{-3} 9.81s 39.08s Timeout 100 2 100 5\cdot 10^{-3} 8.33s Timeout Timeout 100 6 100 5\cdot 10^{-3} 7.97s 34.27s Timeout 100 10 50 5\cdot 10^{-3} 7.79s 37.74s Timeout 100 10 500 5\cdot 10^{-3} 7.99s 43.60s Timeout 100 12 100 5\cdot 10^{-3} 7.61s 37.17s Timeout 100 14 100 5\cdot 10^{-3} 7.95s 45.65s Timeout 100 16 100 5\cdot 10^{-3} 8.09s 38.13s Timeout 100 17 100 5\cdot 10^{-3} Timeout Timeout Timeout 100 18 100 5\cdot 10^{-3} 9.33s 41.75s Timeout 100 18 100 5\cdot 10^{-3} 9.89s 42.29s Timeout 100 19 100 5\cdot 10^{-3} Timeout Timeout Timeout 100 19 100 5\cdot 10^{-3} Timeout Timeout Timeout 100 20 100 5\cdot 10^{-3} 30.54s 41.20s Timeout 100 21 100 5\cdot 10^{-3} Timeout Timeout Timeout 100 22 100 5\cdot 10^{-3} 34.43s 44.97s Timeout 100 10 100 2\cdot 10^{-3} 34.73s Timeout Timeout 100 10 100 1\cdot 10^{-3} 32.49s Timeout Timeout 100 10 100 5\cdot 10^{-4} 33.92s Timeout Timeout 100 10 100 2\cdot 10^{-4} 34.88s Timeout Timeout 100 10 100 1\cdot 10^{-4} Timeout Timeout Timeout 100 18 100 1\cdot 10^{-3} Timeout Timeout Timeout Appendix B Proof of Proposition 2 Recall that L_{c}:=\sup\limits_{x\in\mathcal{B}_{\epsilon}(x_{0})}\sup\limits_{\xi\in\partial_{c}\mu(x)}\|\xi\|_{p,*} , where \|\cdot\|_{p,*} is the dual norm of \|\cdot\|_{p} . In the smooth setting of Proposition 2 , this reduces to L_{c}=\sup\limits_{x\in\mathcal{B}_{\epsilon}(x_{0})}\|\nabla\mu(x)\|_{p,*} . We assume the gradient is \beta -Lipschitz with respect to the same primal-dual norm pair, meaning \|\nabla\mu(x)-\nabla\mu(y)\|_{p,*}\leq\beta\|x-y\|_{p} for all x,y\in\mathcal{B}_{\epsilon}(x_{0}) . In the following proof, we cover the perturbation ball by smaller \ell_{p} balls of radius r . On each small ball, the first-order Taylor approximation to \mu is accurate up to order \frac{\beta r^{2}}{2} . Choosing r=\sqrt{2\tau\epsilon L_{c}/\beta} makes this local approximation error at most \tau\epsilon L_{c} , and the number of required balls gives the stated affine-cover bound. Proof. If L_{c}=0 , then \nabla\mu(x)=0 for all x\in\mathcal{B}_{\epsilon}(x_{0}) , so \mu is constant on the convex set \mathcal{B}_{\epsilon}(x_{0}) . Hence one affine function represents \mu exactly, giving N_{\mathrm{aff}}(\delta)=1 and A_{\tau}^{\star}=0 . The result is therefore immediate. Next, assume L_{c}>0 and let \delta:=\tau\epsilon L_{c} . If \beta=0 , then \nabla\mu is constant on \mathcal{B}_{\epsilon}(x_{0}) , so \mu is affine on \mathcal{B}_{\epsilon}(x_{0}) . Again, N_{\mathrm{aff}}(\delta)=1 and A_{\tau}^{\star}=0 . So, assume \beta>0 and set r:=\sqrt{\frac{2\delta}{\beta}}=\sqrt{\frac{2\tau\epsilon L_{c}}{\beta}}. (72) Let \mathcal{B}_{p}(z,r):=\{x:\|x-z\|_{p}\leq r\} be a closed \ell_{p} ball. By the standard covering-number bound for an \ell_{p} ball, there exist points z_{1},\dots,z_{M}\in\mathcal{B}_{\epsilon}(x_{0}) such that: \mathcal{B}_{\epsilon}(x_{0})\subseteq\bigcup_{i=1}^{M}\left(\mathcal{B}_{p}(z_{i},r)\cap\mathcal{B}_{\epsilon}(x_{0})\right),\;\;\;\;\;M\leq\left(1+\frac{2\epsilon}{r}\right)^{d}. (73) Define U_{i}:=\mathcal{B}_{p}(z_{i},r)\cap\mathcal{B}_{\epsilon}(x_{0}) . Each U_{i} is convex because it is the intersection of two convex sets. For each cell U_{i} , define the first-order affine approximation \ell_{i}(x):=\mu(z_{i})+\nabla\mu(z_{i})^{\top}(x-z_{i}). (74) Fix any x\in U_{i} . By the fundamental theorem of calculus along the segment from z_{i} to x , we have that: \displaystyle\mu(x)-\mu(z_{i}) \displaystyle=\int_{0}^{1}\nabla\mu\bigl(z_{i}+t(x-z_{i})\bigr)^{\top}(x-z_{i})\,dt, (75) \displaystyle\mu(x)-\ell_{i}(x) \displaystyle=\int_{0}^{1}\left[\nabla\mu\bigl(z_{i}+t(x-z_{i})\bigr)-\nabla\mu(z_{i})\right]^{\top}(x-z_{i})\,dt. (76) Using Holder duality and the \beta -Lipschitz property of the gradient: \displaystyle|\mu(x)-\ell_{i}(x)| \displaystyle\leq\int_{0}^{1}\left\|\nabla\mu\bigl(z_{i}+t(x-z_{i})\bigr)-\nabla\mu(z_{i})\right\|_{p,*}\|x-z_{i}\|_{p}\,dt (77) \displaystyle\leq\int_{0}^{1}\beta t\|x-z_{i}\|_{p}^{2}\,dt (78) \displaystyle=\frac{\beta}{2}\|x-z_{i}\|_{p}^{2}. (79) Since x\in U_{i}\subseteq\mathcal{B}_{p}(z_{i},r) , we have \|x-z_{i}\|_{p}\leq r , and hence |\mu(x)-\ell_{i}(x)|\leq\frac{\beta}{2}r^{2}=\delta . Thus each U_{i} admits an affine approximation with error at most \delta , so: N_{\mathrm{aff}}(\delta)\leq M\leq\left(1+\frac{2\epsilon}{r}\right)^{d} (80) Substituting the definition of r gives: \frac{2\epsilon}{r}=2\epsilon\sqrt{\frac{\beta}{2\tau\epsilon L_{c}}}=\sqrt{\frac{2\beta\epsilon}{\tau L_{c}}}=\sqrt{\frac{2\widetilde{\beta}}{\tau}},\qquad\widetilde{\beta}:=\frac{\beta\epsilon}{L_{c}}. (81) Therefore: \displaystyle N_{\mathrm{aff}}(\tau\epsilon L_{c})\leq\left(1+\sqrt{\frac{2\widetilde{\beta}}{\tau}}\right)^{d} (82) \displaystyle\implies A_{\tau}^{\star}=\log N_{\mathrm{aff}}(\tau\epsilon L_{c})\leq d\log\left(1+\sqrt{\frac{2\widetilde{\beta}}{\tau}}\right) (83) ∎ The proposition shows that in smooth networks, affine-cover complexity is controlled by the normalized gradient-variation scale \widetilde{\beta}=\frac{\beta\epsilon}{L_{c}} . In principle, one could estimate \widetilde{\beta} directly and use the bound as a profile component. In practice, however, estimating a global gradient-Lipschitz constant over \mathcal{B}_{\epsilon}(x_{0}) is often conservative, so Section 3 instead uses the empirical statistic A_{\tau} , which samples and counts distinct local linearization classes. For piecewise-linear networks where a global smoothness constant may be infinite, A_{\tau} is interpreted as an empirical count of distinct local affine behaviors encountered inside the perturbation set. Appendix C Verifier Taxonomy by Certificate Type Our characterization of instance difficulty is guided by the wide array of verification algorithm implementations, as the profile must apply to all verifiers. Verification algorithms differ not only in implementation but in the fundamental mathematical object they construct as evidence that \min\limits_{x\in\mathcal{B}_{\epsilon}(x_{0})}\mu(x)>0 . We organize the verifier landscape by certificate type rather than by implementation details such as solver backend or bounding subroutine. We identify four certificate types: Style D (Dual Relaxation). The verifier produces a dual certificate, i.e., a feasible solution to the dual of a convex relaxation of \min\limits_{x\in\mathcal{B}}\mu(x) . Verification terminates in a single pass and no branching or combinatorial search is performed. The quality of the certificate depends entirely on the tightness of the relaxation. Examples: IBP [ 8 ] , CROWN [ 30 ] , \alpha -CROWN [ 27 , 28 ] without branching. Style P (Partition Search). The verifier produces a finite cover \{U_{i}\} of \mathcal{B}_{\epsilon}(x_{0}) together with a bound on \mu over each U_{i} , jointly witnessing \mu>0 on \mathcal{B}_{\epsilon}(x_{0}) . The cover is constructed by recursively splitting the domain and bounding \mu on each piece via relaxation, pruning subproblems whose relaxation already certifies the property. The cost depends on the number of subproblems solved via pruning. Examples: \alpha,\beta -CROWN, Marabou’s divide-and-conquer mode [ 11 ] . Style S (SAT Refutation). The verifier produces a refutation certificate, i.e. a proof that no assignment of activation states is jointly consistent with the constraints implied by \mu(x)\leq 0 . The search is often conducted by a DPLL(T)-style SAT engine [ 6 ] over Boolean activation variables with a solver checking consistency of each partial assignment and learned conflict clauses pruning future candidates. The cost depends on how many partial assignments must be explored before the search space is exhausted. Examples: NeuralSAT [ 5 ] , Marabou’s DPLL(T) engine. Style R (Reachability). The verifier produces a reachability certificate, i.e. an overapproximation of the output range \{f(x):x\in\mathcal{B}_{\epsilon}(x_{0})\} , obtained by propagating an abstract set representation of \mathcal{B}_{\epsilon}(x_{0}) forward through f layer by layer. Unlike other verifier styles, the certificate is typically constructed in the forward direction without explicit duality or domain decomposition, and its cost depends on how the abstract representation grows as it passes through the network f . Examples: nnenum (zonotopes with refinement) [ 3 ] , NNV (star sets) [ 23 ] . Note that several verifiers combine multiple certificate types. For instance, \alpha,\beta -CROWN uses a dual relaxation certificate at each node of a partition search (styles D and P). Similarly, nnenum uses abstract propagation with domain splitting (styles P and R). Appendix D Bug Discovery in Open-Source Verifier During development of VeriStress-GT, we reported a bug in the open-source verifier [Verifier] 1 1 1 Identity of codebase has been redacted to preserve anonymity in the double blind review process. . The issue arose in [Verifier]’s MIP presolve routine for specifications with disjunctive output constraints. In the verifier convention used here, SAT means that the adversarial constraints are feasible, i.e., a counterexample exists, while UNSAT means that no counterexample exists for the given specification. The relevant class of specifications can be written as a disjunction \Phi=\bigvee_{j=1}^{m}\Phi_{j} . Correct handling of such a specification requires OR semantics, i.e. the verifier should return SAT if any disjunct \Phi_{j} is feasible, should return UNSAT only if all disjuncts are infeasible, and should return UNKNOWN if no disjunct is shown feasible but at least one disjunct cannot be resolved. However, the observed behavior in the MIP presolve routine appeared to return the status of the final disjunct checked. As a result, if an earlier disjunct was feasible but the final disjunct was infeasible, the routine could incorrectly return UNSAT on a satisfiable adversarial specification. This failure mode occurred only under a specific combination of conditions. The specification contained multiple disjuncts, at least one non-final disjunct was feasible, the final disjunct in iteration order was infeasible, and MIP presolve was enabled. The reported fix was to aggregate disjunct statuses explicitly. In other words, return SAT immediately upon finding a feasible disjunct and otherwise return UNKNOWN if any disjunct was unresolved, and return UNSAT only after all disjuncts have been proved infeasible. This discovery illustrates one of the motivations for VeriStress-GT. Benchmarks whose labels are inferred from verifier consensus or from the absence of counterexamples can obscure implementation-level soundness failures. By contrast, VeriStress-GT instances have verifier-independent ground-truth robustness labels, allowing incorrect verifier outcomes to be detected directly rather than treated as ambiguous disagreements among tools. We appreciate the responsiveness of the developers of the [Verifier] package in quickly reviewing and approving our proposed fix for this issue. Appendix E Difficulty Profile Study Details E.1 Design Principles Below we state the three major design principles used to guide the process of Difficulty Profile component selection: (D1, Instance-level computability): Each component can be computed without access to the internals of a particular verifier. Thus the difficulty profile component characterizes the problem instance rather than implementation and efficiency details of a verifier. (D2, Certificate Coverage): The components are selected to cover varying bottlenecks in the certification problem. These correspond to fundamentally different reasons a verifier may require branching or refinement and help ensure the Difficulty Profile is applicable to all verifier types (See Appendix C for a description of different verifier styles). (D3, Non-Redundancy and Interpretability): No two components intend to capture the same phenomenon. Otherwise, one may saturate the pool of possible components with many statistics recorded during experimentation, reducing interpretability and leading to a bloated set of components. E.2 Component Search Lastly, we note that many difficulty profile components were tested before decided on the canonical set enumerated in Section 3 . Table 3 below details many of the component ideas that were tested but ultimately not included, typically due to limited correlations with runtime or timeout predictions. Table 3: Difficulty Profile component ideas tested and corresponding explanations as to why they did not appear in the canonical profile defined in Section 3 . Component Idea Intended Signal Reason Discarded Empirical mean margin Average robustness slack over sampled perturbations. Discarded in favor of \widehat{M}_{\min} , which better matches verification failure: a single low-margin region can dominate robustness difficulty even when the average margin is large. IBP absolute gap Raw looseness of interval propagation. Folded into G_{\mathrm{IBP}} . The relative version was more comparable across constructions because raw gaps are strongly affected by logit scale. IBP lower margin Whether plain IBP certifies the instance. Used as a diagnostic, but discarded as a profile component because G_{\mathrm{IBP}} captures relaxation looseness more directly and is measured via a continuous scale Unstable count Number of ambiguous nonlinear units. Folded into U . The fraction normalizes for network size Total nonlinear units Raw nonlinear network size. Discarded because it is mostly a size statistic. U and A_{\tau} better capture whether nonlinearities are actually difficult inside the perturbation set. Raw local pattern count Number of observed local activation patterns. Folded into A_{\tau} . The tolerance-based/log-scaled version was more stable Gradient dimension maximum Worst sampled gradient-dimensionality estimate. Discarded in favor of d_{\mathrm{eff}} mean/aggregate, since the maximum was noisier and more sensitive to outlier samples. Gradient norm Local first-order sensitivity scale. Discarded due to scale dependence and limited standalone intuition. Margin scale and relaxation looseness were better captured by \widehat{M}_{\min} and G_{\mathrm{IBP}} . Gradient sensitivity Variation of gradients across the perturbation set. Discarded because it was noisier than the canonical components. Its useful signal was mostly absorbed by A_{\tau} and d_{\mathrm{eff}} . Gradient concentration Whether sensitivity lies in few coordinates. Folded into d_{\mathrm{eff}} , which gives a more direct and normalized measure of effective sensitivity dimension. Relative linearization error Deviation from first-order local behavior. Discarded due to weaker and less consistent correlation. A_{\tau} gave a cleaner proxy for local piecewise-linear complexity. Absolute linearization error Raw first-order approximation error. Discarded because it is scale-sensitive. The relative version was preferable, but ultimately A_{\tau} had clearer intuition. First-order margin ratio Margin compared to local linear drift. Discarded because it mixed multiple effects. \widehat{M}_{\min} and d_{\mathrm{eff}} separated margin tightness from directional complexity more cleanly. Lipschitz-margin ratio Worst-case sensitivity relative to margin. Discarded because global/local Lipschitz estimates were loose and scale-dependent. \widehat{M}_{\min} and G_{\mathrm{IBP}} were more directly tied to verification outcomes. Estimated local Lipschitz Sampled local sensitivity bound. Discarded due to estimator noise and limited added value beyond gradient- and margin-based canonical components. Curvature proxy Smooth nonlinear bending of the margin. Discarded because estimates were noisy and less natural for ReLU networks. A_{\tau} was a better architecture-agnostic nonlinearity proxy. Parameter count Raw model size. Does not distinguish easy large networks from hard small ones. Layer count Raw network depth. Discarded as too architecture-dependent. Depth can create difficulty, but only through effects better captured by U , A_{\tau} , G_{\mathrm{IBP}} , or d_{\mathrm{eff}} . Instability-region interaction Many unstable units across many local regions. Discarded because it was less interpretable than reporting U and A_{\tau} separately, with limited evidence of consistent added correlation. Looseness-instability interaction Loose relaxations plus many ambiguous units. Discarded because it was mostly redundant with the two canonical components and harder to explain cleanly. Looseness-region interaction Loose relaxations across many regions. Discarded because it added complexity without enough interpretability gain over G_{\mathrm{IBP}} and A_{\tau} . Margin-looseness interaction Small margin plus loose bounds. Discarded because it was highly sensitive when \widehat{M}_{\min} was small. Reporting \widehat{M}_{\min} and G_{\mathrm{IBP}} separately was more stable. Appendix F Numerical Study Details Table 4 displays the aggregated VeriStress-GT stress-test study results, while Table 5 details what hyperparameter ranges were used in each construction for the instantiation of the VeriStress-GT framework. To see the specific configuration for all 225 instances for the stress-test, see “veristress.yaml” and “polynomial \_ stress \_22. yaml” in the configs folder in our public code repository: https://github.com/dtroxell19/VeriStressGT.git Verifier UNSAT SAT Timeout/Unknown Error/Unsupported Total \alpha,\beta -CROWN 193 0 32 0 225 Marabou 122 5 41 57 225 NeuralSAT 188 2 23 12 225 PyRAT 160 0 25 40 225 nnenum 102 1 45 77 225 Table 4: Verification outcomes from Section 4 , aggregated across constructors. Table 5: Constructor hyperparameter ranges for the VeriStress-GT instantiation described in Section 4 . The fixed column lists compact constructor-level constants, while the varied column reports the hyperparameters swept across instances. Note that d represents input dimension and C represents number of output classes. Constructor # Fixed Varied Hyperparameters Hyperparameter Descriptions MEAP 14 d=100 , C=10 P\in\{2,16,32,128\} ; \varepsilon\in\{0.05,0.1,0.25,0.5\} ; \gamma\in\{10^{-5},10^{-4},10^{-3},1,100\} P : ReLU pair count; \varepsilon : perturbation radius; \gamma : certified margin buffer. MILP Exact-Radius 31 d=50 , C=5 h_{1},h_{2}\in\{5,10,20,50,100\} ; \varepsilon_{\mathrm{frac}}\in\{0.5,0.9,0.99,0.999,0.9999,0.99999\} h_{1},h_{2} : hidden-layer widths; \varepsilon_{\mathrm{frac}} : Exact radius multiplier. Input-Corner Stress 22 d=100 , C=10 , \varepsilon=0.2 \texttt{hinge\_l1}\in\{10^{-4},10^{-2},1,10^{2},10^{4},10^{6}\} ; \texttt{num\_hinges}\in\{16,256,1024,4096\} hinge_l1 : hinge slope scale; num_hinges : convex hinge count. Constant-on-Box Embedding 5 d=100 , C=10 , \varepsilon=0.1 \texttt{wide-layers}\in\{1,5,10,20,50\} wide-layers : downstream network depth. Deep Contractive CNN 50 \varepsilon=0.02 , C=10 , k=3 \texttt{depth}\in\{2,4,6,8,10\} ; \texttt{channels}\in\{4,8,16,32,64\} ; \lambda\in\{0.70,0.80,0.90,0.95,0.98\} ; \texttt{margin}\in\{10^{-4},5\cdot 10^{-4},10^{-3},10^{-2},10^{-1}\} ; \texttt{bias\_instability\_frac}\in\{0.10,0.25,0.40,0.55,0.70\} depth : contractive block count; channels : feature-map width; \lambda : per-layer contraction; margin : certified slack floor; bias_instability_frac : instability placement target. Paired-Biases CNN 46 \varepsilon=0.05 , C=10 , k=3 P\in\{2,4,8,16,32\} ; \texttt{margin}\in\{10^{-3},0.05,0.1,0.5,1.0\} ; \delta\in\{0.005,0.01,0.025,0.05,0.1\} ; \texttt{num\_backbone\_layers}\in\{1,2,3,4\} ; H,W\in\{4,8,12,16\} P : paired-channel count; margin : global logit offset; \delta : bias gap half-width; num_backbone_layers : upstream CNN depth; H,W : spatial feature size. Dominant-Key (Linear) Attention 18 C=10 , d_{k}=n n\in\{2,4,6\} ; d\in\{2,4,6,8,12\} ; d_{v}\in\{2,4,8\} ; \varepsilon\in\{0.02,0.05,0.08\} ; \texttt{margin\_factor}\in\{1.1,1.5,2.0,3.0\} ; (\texttt{gate\_scale},\texttt{noise\_scale})\in\{(0.30,0.10),(0.50,0.20),(0.80,0.30)\} n : sequence length; d : token dimension; d_{v} : value dimension; \varepsilon : perturbation radius; margin_factor : certificate headroom; gate_scale : dominant-key strength; noise_scale : off-key suppression. Fixed-Ordering Attention 17 d_{v}=8 , C=50 n\in\{2,8,16,32\} ; d\in\{4,8,16\} ; \alpha\in\{2.0,5.0,10.0\} ; \varepsilon\in\{5\cdot 10^{-4},10^{-3},10^{-2}\} ; \texttt{margin\_slack}\in\{1.00001,1.001,1.05,1.1,2.0,5.0\} n : sequence length; d : token dimension; \alpha : attention score scale; \varepsilon : perturbation radius; margin_slack : certificate headroom. Polynomial Network 22 C = 2 d\in\{50,100\} ; \texttt{degree}\in[2,22] ; h\in\{50,100,500\} ; \delta\in[1\times 10^{-4},5\times 10^{-3}] d : input dimension; degree : polynomial degree; h : hidden width; \delta : boundary buffer. Figure 4: Runtime variability across instances for each constructor/benchmark and verifier. Each cell reports empirical mean \pm standard deviation of runtime in seconds, computed over verified instances and timeouts using the same timing convention as Figure 2 . Verified instances use measured wall-clock time, while timeouts are assigned the benchmark timeout value. Error, unsupported, and unknown outcomes are excluded from the runtime-spread estimate. A cell is left blank if the standard deviation for the runtime was not applicable or 0 . Additionally, we also include trajectory plots showing Difficulty Profile component estimates and corresponding verifier outcomes for each instance in the external MNIST \_ fc and oval 21 benchmarks in Figures 5 and 6 . To access the full csv files containing the difficulty profile estimates and corresponding outcomes (including those for the 225 tested VeriStress-GT framework) please see the Results folder in our public code repository: https://github.com/dtroxell19/VeriStressGT.git Figure 5: Difficulty profile component estimates and verifier outcomes for each of the 90 instances in the MNIST \_ fc VNNCOMP benchmark. Each instance had a timeout limit of 360 seconds per verifier. Figure 6: Difficulty profile component estimates and verifier outcomes for each of the 90 instances in the Oval 21 VNNCOMP benchmark. Each instance had a timeout limit of 360 seconds per verifier. Finally, we also report the distribution of runtimes in Figure 4 , corresponding to the reporting of averages in Figure 2 .