BernBRS:深度伯恩斯坦神经网络的可认证反向可达性
摘要
该论文提出了 BernBRS,这是一种用于对 DeepBernNets 进行可认证后向可达性分析的可扩展框架。该框架通过基于激活模式细化输入空间覆盖,计算后向可达集的经认证内近似和外近似,并在 Half-Cheetah 和基于 TinyBERT 衍生的模型上进行了验证。
查看缓存全文
缓存时间: 2026/11/19 03:36
# Certified Backward Reachability for Deep Bernstein Neural Networks
Source: [https://arxiv.org/html/2611.22083](https://arxiv.org/html/2611.22083)
Conference:30th ACM/IEEE International Conference on Cyber\-Physical and Autonomous Systems; May 17–20, 2027; Boulder, Colorado, USAandYasser ShoukryAffiliation:University of California, Irvine,Irvine,CA,USA
© none
###### Abstract\.
Ensuring the safety of complex neural network systems requires mathematically rigorous verification\. While backward reachability analysis is a critical tool for identifying safe initial states, computing tight, formal bounds remains notoriously difficult to scale\. Recent advancements have demonstrated that DeepBern\-Nets neural networks utilizing Bernstein polynomial activation functions possess advantageous mathematical properties that enable exceptionally fast and tight forward reachability analysis\. Building upon this efficiency, this paper introducesBernBRS, a highly accurate and scalable framework for the backward reachability analysis of DeepBern\-Nets\.BernBRSsimultaneously computes certified inner and outer approximations of the Backward Reachable Set \(BRS\)\. Rather than relying on single convex bounding, our method intelligently refines a cover of the input space by analyzing activation patterns, splitting the input domain precisely where an exact decomposition of the relaxation gap predicts the most significant reduction in error\. This targeted refinement enables high levels of scalability to highly complex and massive architectures that remain intractable for existing certified methods\. We demonstrate the efficacy of our framework on high\-dimensional models, including a linearized closed\-loop approximation of the Half\-Cheetah controller and a distilled Bernstein student of a Transformer block and we empirically study how these model\-level guarantees relate to the original Half\-Cheetah and TinyBERT classifier, respectively\.
###### Keywords:
Backward reachability, Neural Network Verification, Bernstein polynomials, Preimage Approximation\.
## 1\.Introduction
Neural networks \(NNs\) have become foundational components in modern cyber\-physical systems \(CPS\), increasingly serving as complex controllers, advanced perception modules, and learned models of system dynamics\. As these systems are deployed in safety\-critical environments—from autonomous navigation to industrial control—the demand for rigorous, formal guarantees of their behavior is paramount\.
While significant strides have been made in forward verification and reachability analysis\([Katz et al\., 2017](https://arxiv.org/html/2611.22083#bib.bib12);[Zhang et al\., 2018](https://arxiv.org/html/2611.22083#bib.bib38);[Wang et al\., 2021](https://arxiv.org/html/2611.22083#bib.bib37);[Liu et al\., 2021](https://arxiv.org/html/2611.22083#bib.bib17);[Ivanov et al\., 2019](https://arxiv.org/html/2611.22083#bib.bib10);[Dutta et al\., 2019](https://arxiv.org/html/2611.22083#bib.bib4);[Huang et al\., 2019](https://arxiv.org/html/2611.22083#bib.bib9);[Tran et al\., 2020](https://arxiv.org/html/2611.22083#bib.bib34);[Everett et al\., 2021](https://arxiv.org/html/2611.22083#bib.bib5);[Schilling et al\., 2022](https://arxiv.org/html/2611.22083#bib.bib27)\), understanding a system’s complete safety profile requires the ability to reason in reverse\. Backward reachability analysis computes the set of all inputs that lead to a specific output region\([Mitchell et al\., 2005](https://arxiv.org/html/2611.22083#bib.bib20);[Mitchell, 2007](https://arxiv.org/html/2611.22083#bib.bib19);[Bansal et al\., 2017](https://arxiv.org/html/2611.22083#bib.bib2)\), a capability that is uniquely suited to answering fundamental questions about CPS safety and control\. Approximating the backward reachable set \(BRS\) serves three vital purposes: isolating the initial conditions that lead to catastrophic failures, so that any state outside this set can be certified as safe\([Rober et al\., 2023](https://arxiv.org/html/2611.22083#bib.bib26)\), identifying the domain of inputs guaranteed to reach a desired target via inner approximations\([Rober et al\., 2023](https://arxiv.org/html/2611.22083#bib.bib26)\), and providing a mechanism to explain network decision\-making\([Matoba and Fleuret, 2020](https://arxiv.org/html/2611.22083#bib.bib18)\)\. Furthermore, through iterated preimages, this analysis can be extended to verify multi\-step behaviors in closed control loops\([Vincent and Schwager, 2021](https://arxiv.org/html/2611.22083#bib.bib35);[Rober et al\., 2022](https://arxiv.org/html/2611.22083#bib.bib25)\)\.
Despite its critical utility, backward reachability remains notoriously difficult and has received less attention than forward verification\. Neural networks are inherently non\-invertible, meaning multiple inputs can map to the same output\. Consequently, the true BRS is frequently non\-convex, highly disjointed, and topologically complex\. Exact backward analysis has largely been restricted to piecewise\-affine architectures, such as ReLU networks, using computationally exhaustive techniques like polyhedral marching\([Vincent and Schwager, 2021](https://arxiv.org/html/2611.22083#bib.bib35)\)or activation region enumeration\([Matoba and Fleuret, 2020](https://arxiv.org/html/2611.22083#bib.bib18)\)\. To manage this complexity, approximation frameworks relax the network with linear bounds\. INVPROP\([Kotha et al\., 2023](https://arxiv.org/html/2611.22083#bib.bib14)\)computes outer bounds only, and PREMAP\([Zhang et al\., 2025](https://arxiv.org/html/2611.22083#bib.bib39)\)computes an inner or an outer set in separate runs\. The backward reachability method of Rober et al\.\([Rober et al\., 2022](https://arxiv.org/html/2611.22083#bib.bib25);[Rober et al\., 2023](https://arxiv.org/html/2611.22083#bib.bib26)\), which uses the linear relaxations of CROWN\([Zhang et al\., 2018](https://arxiv.org/html/2611.22083#bib.bib38)\), computes outer bounds and keeps one hyper\-rectangle per time step, which can be conservative\. INVPROP and PREMAP reduce this looseness with unions of convex sets over input splits, and PREMAP also splits on ReLU neurons\. Both are formulated for ReLU networks\.
Recent advancements have demonstrated that DeepBern\-Nets\([Khedr and Shoukry, 2024](https://arxiv.org/html/2611.22083#bib.bib13)\)neural network architectures utilizing Bernstein polynomial activation functions offer uniquely advantageous mathematical properties for verification\. Specifically, their inherent polynomial structure has been exploited to compute tight forward bounds, in a few seconds even for networks with millions of parameters\. Building upon this unprecedented efficiency, this paper asks the question: can we extend these properties to the backward domain? To answer this, we establish a highly accurate and scalable backward reachability framework for DeepBern\-Nets\. We introduceBernBRS, a novel algorithmic approach that simultaneously computes certified inner and outer approximations of the Backward Reachable Set \(BRS\)\. Our method intelligently refines a cover of the input space by analyzing activation patterns, splitting the input domain precisely where an exact decomposition of the relaxation gap predicts the most significant reduction in error\. The specific contributions of this work are as follows:
- •TheBernBRSFramework: We propose a comprehensive method for computing certified inner and outer approximations of the backward reachable set of DeepBern\-Nets\([Khedr and Shoukry, 2024](https://arxiv.org/html/2611.22083#bib.bib13)\), guaranteeing mathematical soundness at every refinement iteration\.
- •Gap\-Driven Refinement: We introduce an advanced branching strategy that partitions the input space based on an exact decomposition of the relaxation gap\.
- •Scalability to Complex Architectures: Our framework demonstrates scalability to a diverse range of massive and complex architectures that, to our knowledge, have not previously been handled by certified backward reachability methods\. This includes \(i\) a merged DeepBern\-Net representation of a linearized Half\-Cheetah closed loop, and \(ii\) a Bernstein distilled transformer block and classifier of a TinyBERT model\. In both cases,BernBRSprovides mathematically rigorous backward reachability bounds for these surrogate networks; the connection to the underlying MuJoCo simulator and to TinyBERT is evaluated empirically rather than formally certified\.
## 2\.Problem Setup
### 2\.1\.Notation
Letℝ\\mathbb\{R\}and\[N\]\[N\]denote the set of Real and finite set of positive integers \(i\.e\.,\[N\]=\{1,…,N\}\[N\]=\\\{1,\\dots,N\\\}for an integerN≥1N\\geq 1\), respectively\. For a matrixWW,W\+=max\(W,0\)W^\{\+\}=\\max\(W,0\),W−=min\(W,0\)W^\{\-\}=\\min\(W,0\)and\|W\|\|W\|act entrywise, andWj:W\_\{j:\}is thejj\-th row\. Vector inequalities hold entrywise\. A*box*isX=\[x¯,x¯\]=∏i=1d\[x¯i,x¯i\]X=\[\\underline\{x\},\\overline\{x\}\]=\\prod\_\{i=1\}^\{d\}\[\\underline\{x\}\_\{i\},\\overline\{x\}\_\{i\}\]wherex¯,x¯∈ℝd\\underline\{x\},\\overline\{x\}\\in\\mathbb\{R\}^\{d\}, with edge lengthshi\(X\)=x¯i−x¯ih\_\{i\}\(X\)=\\overline\{x\}\_\{i\}\-\\underline\{x\}\_\{i\}\. For a finite family𝒮\\mathcal\{S\}of sets,⋃𝒮\\bigcup\\mathcal\{S\}is their union\. An*interval vector*\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]*encloses*a mapφ\\varphion a setSSifφ\(S\)⊆\[z¯,z¯\]\\varphi\(S\)\\subseteq\[\\underline\{z\},\\overline\{z\}\]\. The symbolvol\(S\)\\vol\(S\)is the Lebesgue measure of the setSS\.
zzσ\(z\)\\sigma\(z\)ℓ\\elluuc0c\_\{0\}c1c\_\{1\}c2c\_\{2\}c3c\_\{3\}z¯\\underline\{z\}z¯\\overline\{z\}Figure 1\.A Bernstein activation with its control points and an interval\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]inside its bounds\.
### 2\.2\.Bernstein Polynomials
In this paper, we focus on neural networks that follow the DeepBern\-Nets\([Khedr and Shoukry, 2024](https://arxiv.org/html/2611.22083#bib.bib13)\)architecture whose activations are based on the Bernstein polynomials\. For an interval\[ℓ,u\]\[\\ell,u\]withℓ<u\\ell<u, the Bernstein basis polynomials of degreennare:
\(1\)Bn,i\[ℓ,u\]\(z\)=\(ni\)\(z−ℓ\)i\(u−z\)n−i\(u−ℓ\)n,i=0,…,n\.B^\{\[\\ell,u\]\}\_\{n,i\}\(z\)=\\binom\{n\}\{i\}\\frac\{\(z\-\\ell\)^\{i\}\\,\(u\-z\)^\{n\-i\}\}\{\(u\-\\ell\)^\{n\}\},\\qquad i=0,\\dots,n\.A polynomialqqof degree at mostnnhas a unique form:
\(2\)q\(z\)=∑i=0nciBn,i\[ℓ,u\]\(z\)\.q\(z\)=\\sum\_\{i=0\}^\{n\}c\_\{i\}\\,B^\{\[\\ell,u\]\}\_\{n,i\}\(z\)\.The vectorc=\(c0,…,cn\)c=\(c\_\{0\},\\dots,c\_\{n\}\)holds the*Bernstein coefficients*ofqqon\[ℓ,u\]\[\\ell,u\]\. We use the following properties ofqq\([Khedr and Shoukry, 2024](https://arxiv.org/html/2611.22083#bib.bib13);[Ramshaw, 1989](https://arxiv.org/html/2611.22083#bib.bib24);[Prautzsch et al\., 2002](https://arxiv.org/html/2611.22083#bib.bib21);[Farouki, 2012](https://arxiv.org/html/2611.22083#bib.bib6)\)\.
1. \(P1\)*Enclosure of range*\([Farouki, 2012](https://arxiv.org/html/2611.22083#bib.bib6)\)\.minici≤q\(z\)≤maxici\\min\_\{i\}c\_\{i\}\\leq q\(z\)\\leq\\max\_\{i\}c\_\{i\}forz∈\[ℓ,u\]z\\in\[\\ell,u\], withq\(ℓ\)=c0q\(\\ell\)=c\_\{0\}andq\(u\)=cnq\(u\)=c\_\{n\}\.
2. \(P2\)*Subdivision*\([Prautzsch et al\., 2002](https://arxiv.org/html/2611.22083#bib.bib21)\)\. Forℓ≤ℓ′<u′≤u\\ell\\leq\\ell^\{\\prime\}<u^\{\\prime\}\\leq u, the Bernstein coefficientsc′c^\{\\prime\}ofqqon\[ℓ′,u′\]\[\\ell^\{\\prime\},u^\{\\prime\}\]follow fromccby de Casteljau steps in𝒪\(n2\)\\mathcal\{O\}\(n^\{2\}\)operations, and eachci′c^\{\\prime\}\_\{i\}is a convex combination of the entries ofcc\. Forℓ′=u′\\ell^\{\\prime\}=u^\{\\prime\}we setci′=q\(ℓ′\)c^\{\\prime\}\_\{i\}=q\(\\ell^\{\\prime\}\)for allii\.
3. \(P3\)*Derivative*\([Farouki, 2012](https://arxiv.org/html/2611.22083#bib.bib6)\)\.q′\(z\)=nu−ℓ∑i=0n−1\(ci\+1−ci\)Bn−1,i\[ℓ,u\]\(z\)q^\{\\prime\}\(z\)=\\tfrac\{n\}\{u\-\\ell\}\\sum\_\{i=0\}^\{n\-1\}\(c\_\{i\+1\}\-c\_\{i\}\)\\,B^\{\[\\ell,u\]\}\_\{n\-1,i\}\(z\)\.
4. \(P4\)*Linear precision\.*The Bernstein coefficients of degreennof the affine mapz↦α\+szz\\mapsto\\alpha\+szon\[ℓ,u\]\[\\ell,u\]areci=α\+s\(ℓ\+\(u−ℓ\)i/n\)c\_\{i\}=\\alpha\+s\\,\\big\(\\ell\+\(u\-\\ell\)\\,i/n\\big\)for allii\.
### 2\.3\.Bernstein Neural Networks
###### Definition 2\.1 \(Bernstein neural network\([Khedr and Shoukry, 2024](https://arxiv.org/html/2611.22083#bib.bib13)\)\)\.
A Bernstein neural network withRRhidden layers of widthswrw\_\{r\}, input dimensionddand output dimensionmmis the mapf:ℝd→ℝmf:\\mathbb\{R\}^\{d\}\\to\\mathbb\{R\}^\{m\}defined by:
\(3\)z\(0\)\(x\)=x,z\(r\)\(x\)=Wrσ\(r−1\)\(z\(r−1\)\(x\)\)\+br,\\displaystyle z^\{\(0\)\}\(x\)=x,\\quad z^\{\(r\)\}\(x\)=W\_\{r\}\\,\\sigma^\{\(r\-1\)\}\\big\(z^\{\(r\-1\)\}\(x\)\\big\)\+b\_\{r\},f\(x\)=WR\+1σ\(R\)\(z\(R\)\(x\)\)\+bR\+1,\\displaystyle f\(x\)=W\_\{R\+1\}\\,\\sigma^\{\(R\)\}\\big\(z^\{\(R\)\}\(x\)\\big\)\+b\_\{R\+1\},forr∈\[R\]r\\in\[R\], wherez\(r\)\(x\)z^\{\(r\)\}\(x\)is the vector of pre\-activations of layerrr,σ\(0\)\\sigma^\{\(0\)\}is the identity andσ\(r\)\\sigma^\{\(r\)\}applies the activationσj\(r\)\\sigma^\{\(r\)\}\_\{j\}of neuron\(r,j\)\(r,j\)to coordinatejj\. Neuron\(r,j\)\(r,j\)has a degreenrn\_\{r\}, bounds\[ℓj\(r\),uj\(r\)\]\[\\ell^\{\(r\)\}\_\{j\},u^\{\(r\)\}\_\{j\}\]withℓj\(r\)<uj\(r\)\\ell^\{\(r\)\}\_\{j\}<u^\{\(r\)\}\_\{j\}on its pre\-activation, and Bernstein coefficientscj\(r\)∈ℝnr\+1c^\{\(r\)\}\_\{j\}\\in\\mathbb\{R\}^\{n\_\{r\}\+1\}\. Its activation is:
\(4\)σ\(z,ℓ,u,c\)\\displaystyle\\sigma\(z;\\ell,u,c\)=∑i=0nrciBnr,i\[ℓ,u\]\(z\),σj\(r\)\(z\)\\displaystyle=\\sum\_\{i=0\}^\{n\_\{r\}\}c\_\{i\}\\,B^\{\[\\ell,u\]\}\_\{n\_\{r\},i\}\(z\),\\quad\\sigma^\{\(r\)\}\_\{j\}\(z\)=σ\(z,ℓj\(r\),uj\(r\),cj\(r\)\)\.\\displaystyle=\\sigma\\big\(z;\\ell^\{\(r\)\}\_\{j\},u^\{\(r\)\}\_\{j\},c^\{\(r\)\}\_\{j\}\\big\)\.
For layerrrWr∈ℝwr×wr−1W\_\{r\}\\in\\mathbb\{R\}^\{w\_\{r\}\\times w\_\{r\-1\}\}andbr∈ℝwrb\_\{r\}\\in\\mathbb\{R\}^\{w\_\{r\}\}denote the weight matrix and bias vector of layerrr, respectively\.d∈ℕd\\in\\mathbb\{N\}is the input dimension\.
### 2\.4\.Activation Patterns
To systematically analyze the network’s non\-linear behavior, we must first break down its operation into tractable components\. We achieve this by introducing*activation patterns*, which constrain the activation functions to specific intervals and allow us to identify the precise subsets of the input domain that lead to those states\.
###### Definition 2\.2 \(Activation pattern\)\.
An*activation pattern*is defined asP=\(X^,Z^\)P=\(\\hat\{X\},\\hat\{Z\}\)such that:
1. \(1\)X^⊆ℝd\\hat\{X\}\\subseteq\\mathbb\{R\}^\{d\}is a box of network inputs,
2. \(2\)Z^=\{Z^\(1\),…,Z^\(R\)\}\\hat\{Z\}=\\\{\\hat\{Z\}^\{\(1\)\},\\dots,\\hat\{Z\}^\{\(R\)\}\\\}\. For each layerr∈\[R\]r\\in\[R\]the intervalZ^\(r\)=\[z¯^\(r\),z^¯\(r\)\]⊆ℝwr\\hat\{Z\}^\{\(r\)\}=\[\\underline\{\\vphantom\{\\overline\{\\hat\{z\}\}\}\\hat\{z\}\}^\{\(r\)\},\\overline\{\\hat\{z\}\}^\{\(r\)\}\]\\subseteq\\mathbb\{R\}^\{w\_\{r\}\}\.
Each activation pattern is associated with a*region*ℛ\(P\)\\mathcal\{R\}\(P\)defined as:
\(5\)ℛ\(P\)=\{x∈X^:z\(r\)\(x\)∈Z^\(r\)for allr∈\[R\]\}\.\\mathcal\{R\}\(P\)=\\big\\\{x\\in\\hat\{X\}:z^\{\(r\)\}\(x\)\\in\\hat\{Z\}^\{\(r\)\}\\text\{ for all \}r\\in\[R\]\\big\\\}\.The regionℛ\(P\)\\mathcal\{R\}\(P\)is non\-convex in general\.
InputsPriority queueForward boundingBackward contractionBranchingOutputDeepBern\-Netffinput box𝒳\\mathcal\{X\}target𝒴=\{y:Hy≤h\}\\mathcal\{Y\}\{=\}\\\{y\{:\}Hy\{\\leq\}h\\\}budgetNN, batchBBP1P\_\{1\}P2P\_\{2\}P3P\_\{3\}batchℬ\\mathcal\{B\}⋯\\cdotslargest volume firstinitialpartitionτ\+1\\tau\{\+\}1roundsundecidedchildren enterthe priority queueoutput on the patternlinear boundsLL,UUtarget𝒴\\mathcal\{Y\}removed by contraction𝒳\\mathcal\{X\}⋃𝒪\\bigcup\\mathcal\{O\}BRSf\(𝒴\)\\BRS\_\{f\}\(\\mathcal\{Y\}\)⋃ℐ\\bigcup\\mathcal\{I\}P1P\_\{1\}P1P\_\{1\}P1P\_\{1\}P2P\_\{2\}P2P\_\{2\}P2P\_\{2\}P3P\_\{3\}P3P\_\{3\}P3P\_\{3\}Figure 2\.Algorithmic Architecture of theBernBRSFramework\. The algorithm begins by partitioning the input domain𝒳\\mathcal\{X\}into a priority queue ranked by estimated volume\. In each iteration, the largest patterns undergo forward bounding to establish parallel linear bounds \(L,UL,U\) enclosing the output\. Backward contraction subsequently discards inputs violating the target conditionf\(x\)∉𝒴f\(x\)\\notin\\mathcal\{Y\}\(faded regions\)\. Forward bounding and backward contraction alternate cyclically forτ\+1\\tau\+1rounds\. Undecided patterns branch into refined children and re\-enter the queue, while certified regions form the final inner \(⋃ℐ\\bigcup\\mathcal\{I\}\) and outer \(⋃𝒪\\bigcup\\mathcal\{O\}\) approximations of the target set\.
### 2\.5\.Backward Reachable Sets
To define the problem of interest, we assume an input domain defined as a bounding box𝒳⊂ℝd\\mathcal\{X\}\\subset\\mathbb\{R\}^\{d\}\. We define our target𝒴⊂ℝm\\mathcal\{Y\}\\subset\\mathbb\{R\}^\{m\}a polyhedron represented by a system of inequalities:
\(6\)𝒴=\{y∈ℝm:Hy≤h\},H∈ℝmH×m,h∈ℝmH,\\mathcal\{Y\}=\\\{y\\in\\mathbb\{R\}^\{m\}:Hy\\leq h\\\},\\qquad H\\in\\mathbb\{R\}^\{m\_\{H\}\\times m\},\\;h\\in\\mathbb\{R\}^\{m\_\{H\}\},
###### Definition 2\.3 \(Backward reachable set\)\.
For a given mapping functionf:𝒳→ℝmf:\\mathcal\{X\}\\rightarrow\\mathbb\{R\}^\{m\}and a target𝒴⊂ℝm\\mathcal\{Y\}\\subset\\mathbb\{R\}^\{m\}, the backward reachable set \(BRS\) consists of all inputs points in𝒳\\mathcal\{X\}that maps to the target polyhedron𝒴\\mathcal\{Y\}, that is,BRSf\(𝒴\)=\{x∈𝒳:f\(x\)∈𝒴\}\\BRS\_\{f\}\(\\mathcal\{Y\}\)=\\\{x\\in\\mathcal\{X\}:f\(x\)\\in\\mathcal\{Y\}\\\}\.
We can now state the problem studied in this paper as follows\.
###### Problem 1 \(Certified BRS approximation\)\.
Given a Bernstein neural networkff, an input domain𝒳\\mathcal\{X\}, and a target𝒴\\mathcal\{Y\}, find finite collectionsℐ\\mathcal\{I\}and𝒪\\mathcal\{O\}of subsets of𝒳\\mathcal\{X\}, with each subset of the formℛ\(P\)∩\{x:Ax≤c\}\\mathcal\{R\}\(P\)\\cap\\\{x:Ax\\leq c\\\}, such that
\(7\)⋃ℐ⊆BRSf\(𝒴\)⊆⋃𝒪\.\\bigcup\\mathcal\{I\}\\;\\subseteq\\;\\BRS\_\{f\}\(\\mathcal\{Y\}\)\\;\\subseteq\\;\\bigcup\\mathcal\{O\}\.
The combined region defined byℐ\\mathcal\{I\}forms the*inner*approximation; it provides a strict guarantee that any inputxxfound within it will successfully map to the target \(f\(x\)∈𝒴f\(x\)\\in\\mathcal\{Y\}\)\. Conversely, the combined region defined by𝒪\\mathcal\{O\}forms the*outer*approximation; it guarantees that any inputx∈𝒳x\\in\\mathcal\{X\}falling strictly outside of this combined region will fail to reach the target \(f\(x\)∉𝒴f\(x\)\\notin\\mathcal\{Y\}\)\.
## 3\.Overview of theBernBRSFramework
As shown in Figure[2](https://arxiv.org/html/2611.22083#S2.F2)and Algorithms[1](https://arxiv.org/html/2611.22083#alg1)and[2](https://arxiv.org/html/2611.22083#alg2),BernBRScomputes certified inner and outer approximations of the BRS of a Bernstein neural network\. Its inputs are the networkff, the input box𝒳\\mathcal\{X\}, the polyhedral target𝒴=\{y:Hy≤h\}\\mathcal\{Y\}=\\\{y:Hy\\leq h\\\}and a budget ofNNpatterns \(or partitions\)\. Its outputs are two finite collections of setsℐ\\mathcal\{I\}and𝒪\\mathcal\{O\}with⋃ℐ⊆BRSf\(𝒴\)⊆⋃𝒪\\bigcup\\mathcal\{I\}\\subseteq\\BRS\_\{f\}\(\\mathcal\{Y\}\)\\subseteq\\bigcup\\mathcal\{O\}\. The overarching architecture of this approach relies on a continuous, iterative cycle of bounding, contraction, and branching, initialized by establishing a root pattern that encapsulates the entire input domain𝒳\\mathcal\{X\}and inserting it into a volumetrically prioritized queue,𝒬\\mathcal\{Q\}\(Algorithm[1](https://arxiv.org/html/2611.22083#alg1), line 1\)\. Algorithm[1](https://arxiv.org/html/2611.22083#alg1)gives the loop over this queue, and Algorithm[2](https://arxiv.org/html/2611.22083#alg2)gives the processing of one pattern\.
Fundamental to theBernBRSframework is the partitioning of the input space via activation patterns, which explicitly couple an input spatial box with a specific pre\-activation interval for every neuron within the network architecture\. To evaluate these patterns, the system employs forward bounding \(Algorithm[2](https://arxiv.org/html/2611.22083#alg2), line 2\), sequentially computing limits from the input layer through to the final output layer\. This is achieved through interval bound propagation, wherein the post\-activation intervals of one layer dictate the pre\-activation intervals of the subsequent layer via affine mapping\. During this forward pass, each non\-linear activation function is strictly enclosed by parallel upper and lower affine bounds\. The vertical distance separating these parallel lines defines the relaxation width for each individual neuron\. By back\-substituting these relaxations through the network layers, the algorithm ultimately generates linear lower bounds,Li\(x\)L\_\{i\}\(x\), and upper bounds,Ui\(x\)U\_\{i\}\(x\), over the target rows for all inputs contained within the specified pattern\.
Following the forward pass, the framework implements a backward contraction pass \(Algorithm[2](https://arxiv.org/html/2611.22083#alg2), line 7\) designed to systematically identify and prune input sub\-regions that demonstrably fail to map into the polyhedral target\. This contraction operates in reverse, propagating constraints from the network output back toward the input domain\. Initially, the defined target boundaries and the output layer weights are utilized to narrow the post\-activation intervals of the final hidden layer\. Subsequently, neurons that are mathematically certified as monotone undergo an inversion process\. This mathematical inversion allows the tighter post\-activation limits to iteratively constrain and shrink their corresponding pre\-activation intervals\. To maximize the reduction of the pattern’s geometric region, this contraction pass alternates with forward bounding for up toτ\+1\\tau\+1rounds \(Algorithm[2](https://arxiv.org/html/2611.22083#alg2), lines 1–12\)\.
The algorithm continuously evaluates its progress toward definitive classification by measuring the gap between the computed bounds, mathematically defined asδi=Ui\(x\)−Li\(x\)\\delta\_\{i\}=U\_\{i\}\(x\)\-L\_\{i\}\(x\)\. A target row achieves certified satisfaction if its corresponding upper bound remains strictly less than or equal to the defined target threshold, expressed asUi\(x\)≤hiU\_\{i\}\(x\)\\leq h\_\{i\}for allxxin the pattern \(Algorithm[2](https://arxiv.org/html/2611.22083#alg2), line 5\)\. Conversely, if the lower bound exceeds this threshold \(Li\(x\)\>hiL\_\{i\}\(x\)\>h\_\{i\}for allxxin the pattern\), the row is certified as violated, and the corresponding spatial region is entirely pruned from the search space\. Patterns where the bounds cross the threshold are designated as undecided\. For these undecided regions, the verified inner subsets are dynamically allocated to the collectionℐ\\mathcal\{I\}, while their enveloping outer subsets are concurrently allocated to𝒪\\mathcal\{O\}\(Algorithm[2](https://arxiv.org/html/2611.22083#alg2), lines 13 and 19\)\.
To resolve undecided patterns and refine the computational bounds, the framework employs a gap\-driven branching strategy \(Algorithm[2](https://arxiv.org/html/2611.22083#alg2), line 15\) that partitions these regions into smaller child patterns\. A naive approach of bisecting every interval would induce an intractable exponential explosion\. For instance, a400400\-neuron network would theoretically generate up to24002^\{400\}child patterns\. To ensure computational scalability,BernBRScomputes reduction scores for both input dimensions and individual neurons to identify the specific split that is expected to reduce the target gap the most\. If an input dimension yields the highest score, a standard spatial split is executed, yielding two distinct child patterns\. Alternatively, if neurons achieve higher reduction scores, the system executes a “joint split” across a selected subset of neurons\. This joint splitting mechanism utilizes the means and standard deviations of uniform samples to tightly confine the selected neurons to a narrow central interval\. By strategically nesting these restrictions, splittingppneurons generates at most2p\+12p\+1children, vastly outperforming the exponential3p3^\{p\}growth that would otherwise occur without such statistical confinement\.
The orchestration of this entire verification procedure is governed by a priority queue that continuously ranks pending activation patterns based on their estimated volumetric size relative to the original input bounding box𝒳\\mathcal\{X\}\. During each iterative round, the algorithm extracts a batch consisting of up toBBpatterns that exhibit the largest estimated volumes \(Algorithm[1](https://arxiv.org/html/2611.22083#alg1), line 3\) and processes them in parallel with Algorithm[2](https://arxiv.org/html/2611.22083#alg2)\(Algorithm[1](https://arxiv.org/html/2611.22083#alg1), lines 5–7\)\. The computational process officially terminates either when the priority queue𝒬\\mathcal\{Q\}is completely emptied or when the pre\-allocated pattern budgetNNis fully exhausted \(Algorithm[1](https://arxiv.org/html/2611.22083#alg1), line 2\)\. Upon termination, any patterns that remain unresolved within the queue are subjected to a final classification pass \(Algorithm[1](https://arxiv.org/html/2611.22083#alg1), lines 10–14\), after which their respective geometric regions are formally finalized and sorted into the ultimate output collectionsℐ\\mathcal\{I\}and𝒪\\mathcal\{O\}\. We provide technical details of each of the three components \(bounding, contraction, and branching\) in the next sections\.
Algorithm 1BernBRS: parallel refinement over activation patterns1:Network
ff, input box
𝒳\\mathcal\{X\}, target
𝒴=\{Hy≤h\}\\mathcal\{Y\}=\\\{Hy\\leq h\\\}, budget
NN, batch size
BB, volume gate
γ∈\(0,1\]\\gamma\\in\(0,1\]
2:Collections
ℐ\\mathcal\{I\},
𝒪\\mathcal\{O\}satisfying \([7](https://arxiv.org/html/2611.22083#S2.E7)\)
3:
𝒬←\\mathcal\{Q\}\\leftarrowthe root pattern, or the initial partition;
ℐ,𝒪←∅\\mathcal\{I\},\\mathcal\{O\}\\leftarrow\\emptyset;
ν←0\\nu\\leftarrow 0
4:while
𝒬≠∅\\mathcal\{Q\}\\neq\\emptysetand
ν<N\\nu<Ndo⊳\\trianglerightrefinement rounds
5:
ℬ←\\mathcal\{B\}\\leftarrowthe patterns of
𝒬\\mathcal\{Q\}of largest estimated volume, at most
min\(B,N−ν\)\\min\(B,N\-\\nu\), each of estimated volume at least
γ\\gammatimes the largest
6:
𝒬←𝒬∖ℬ\\mathcal\{Q\}\\leftarrow\\mathcal\{Q\}\\setminus\\mathcal\{B\};
ν←ν\+\|ℬ\|\\nu\\leftarrow\\nu\+\|\\mathcal\{B\}\|
7:foreach
P∈ℬP\\in\\mathcal\{B\}in paralleldo
8:
𝑟𝑒𝑠P←ProcessPattern\(P,true\)\\mathit\{res\}\_\{P\}\\leftarrow\\textsc\{ProcessPattern\}\(P,\\textsc\{true\}\)⊳\\trianglerightAlg\.[2](https://arxiv.org/html/2611.22083#alg2)
9:endfor
10:Collect\(\{𝑟𝑒𝑠P\}\)\(\\\{\\mathit\{res\}\_\{P\}\\\}\)
11:endwhile
12:
𝒬′←𝒬\\mathcal\{Q\}^\{\\prime\}\\leftarrow\\mathcal\{Q\}, or the
min\(N,\|𝒬\|\)\\min\(N,\|\\mathcal\{Q\}\|\)patterns of
𝒬\\mathcal\{Q\}of largest estimated volume⊳\\trianglerightfinal classification
13:foreach
P∈𝒬′P\\in\\mathcal\{Q\}^\{\\prime\}in paralleldo
14:
𝑟𝑒𝑠P←ProcessPattern\(P,false\)\\mathit\{res\}\_\{P\}\\leftarrow\\textsc\{ProcessPattern\}\(P,\\textsc\{false\}\)
15:endfor
16:Collect\(\{𝑟𝑒𝑠P\}\)\(\\\{\\mathit\{res\}\_\{P\}\\\}\);
𝒪←𝒪∪\{ℛ\(P\):P∈𝒬∖𝒬′\}\\mathcal\{O\}\\leftarrow\\mathcal\{O\}\\cup\\\{\\mathcal\{R\}\(P\):P\\in\\mathcal\{Q\}\\setminus\\mathcal\{Q\}^\{\\prime\}\\\}
17:return
\(ℐ,𝒪\)\(\\mathcal\{I\},\\mathcal\{O\}\)
Algorithm 2ProcessPattern\(P,s\)\\textsc\{ProcessPattern\}\(P,s\)1:Pattern
P=\(X^,Z^\)P=\(\\hat\{X\},\\hat\{Z\}\), splitting flag
ss, contraction rounds
τ\\tau, depth limit
DD
2:for
t=0,…,τt=0,\\dots,\\taudo
3:
ℬP,\(L,U\)←\\mathcal\{B\}\_\{P\},\(L,U\)\\leftarrowcertified bounds over
ℛ\(P\)\\mathcal\{R\}\(P\)⊳\\trianglerightbounding, Alg\.[3](https://arxiv.org/html/2611.22083#alg3)
4:if
ℬP\\mathcal\{B\}\_\{P\}is emptyorsome row is certified violatedthenreturnprune
5:endif
6:ifevery row is certified satisfiedthenreturn
accept\(ℛ\(P\)\)\\textsc\{accept\}\(\\mathcal\{R\}\(P\)\)
7:endif
8:
P′←P^\{\\prime\}\\leftarrowcontraction of
PPagainst
𝒴\\mathcal\{Y\}⊳\\trianglerightAlg\.[4](https://arxiv.org/html/2611.22083#alg4)
9:if
P′P^\{\\prime\}is emptythenreturnprune
10:endif
11:if
t<τt<\\tauthen
P←P′P\\leftarrow P^\{\\prime\}
12:endif
13:endfor
14:
I←ℛ\(P′\)∩\{U\(x\)≤h\}I\\leftarrow\\mathcal\{R\}\(P^\{\\prime\}\)\\cap\\\{U\(x\)\\leq h\\\},
O←ℛ\(P′\)∩\{L\(x\)≤h\}O\\leftarrow\\mathcal\{R\}\(P^\{\\prime\}\)\\cap\\\{L\(x\)\\leq h\\\}
15:if
ssand
depth\(P\)<D\\mathrm\{depth\}\(P\)<Dthen
16:
𝒞←Refine\(P′,L,U\)\\mathcal\{C\}\\leftarrow\\textsc\{Refine\}\(P^\{\\prime\},L,U\)⊳\\trianglerightbranching, Alg\.[5](https://arxiv.org/html/2611.22083#alg5)
17:if
𝒞≠∅\\mathcal\{C\}\\neq\\emptysetthenreturn
split\(𝒞\)\\textsc\{split\}\(\\mathcal\{C\}\)
18:endif
19:endif
20:return
undecided\(I,O\)\\textsc\{undecided\}\(I,O\)
## 4\.Forward Bounding
This section explains the mathematical steps behind the forward bounding method\. Forward bounding is a crucial step used to safely estimate the range of possible outputs of each neuron\. We provide the complete, step\-by\-step process in Algorithm[3](https://arxiv.org/html/2611.22083#alg3)\. All mathematical proofs are included in Appendix[A](https://arxiv.org/html/2611.22083#A1)\.
### 4\.1\.Interval Propagation over a Pattern
For every activation patternP=\(X^,Z^\)P=\(\\hat\{X\},\\hat\{Z\}\)prioritized within the queue𝒬\\mathcal\{Q\}, the procedure starts by applying the interval bound propagation from\([Khedr and Shoukry, 2024](https://arxiv.org/html/2611.22083#bib.bib13)\), restricted to the pattern\. This propagation starts from\[σ¯\(0\),σ¯\(0\)\]=X^\[\\underline\{\\sigma\}^\{\(0\)\},\\overline\{\\sigma\}^\{\(0\)\}\]=\\hat\{X\}and proceeds iteratively to derive rigorous bounds for each subsequent layerr∈\[R\]r\\in\[R\]\. The bounds are computed as:
z¯\(r\)\\displaystyle\\underline\{z\}^\{\(r\)\}=max\(Wr\+σ¯\(r−1\)\+Wr−σ¯\(r−1\)\+br,z¯^\(r\)\),\\displaystyle=\\max\\big\(W\_\{r\}^\{\+\}\\underline\{\\sigma\}^\{\(r\-1\)\}\+W\_\{r\}^\{\-\}\\overline\{\\sigma\}^\{\(r\-1\)\}\+b\_\{r\},\\;\\underline\{\\hat\{z\}\}^\{\(r\)\}\\big\),\(8\)z¯\(r\)\\displaystyle\\overline\{z\}^\{\(r\)\}=min\(Wr\+σ¯\(r−1\)\+Wr−σ¯\(r−1\)\+br,z^¯\(r\)\),\\displaystyle=\\min\\big\(W\_\{r\}^\{\+\}\\overline\{\\sigma\}^\{\(r\-1\)\}\+W\_\{r\}^\{\-\}\\underline\{\\sigma\}^\{\(r\-1\)\}\+b\_\{r\},\\;\\overline\{\\hat\{z\}\}^\{\(r\)\}\\big\),\(9\)\[σ¯j\(r\),σ¯j\(r\)\]\\displaystyle\[\\underline\{\\sigma\}^\{\(r\)\}\_\{j\},\\overline\{\\sigma\}^\{\(r\)\}\_\{j\}\]=\[minici′,maxici′\]\.\\displaystyle=\\big\[\\min\_\{i\}c^\{\\prime\}\_\{i\},\\max\_\{i\}c^\{\\prime\}\_\{i\}\\big\]\.The specific Bernstein coefficientsc′c^\{\\prime\}are systematically derived by leveraging the subdivision property \(Property P2\), which mathematically restricts the polynomial activation domain for each individual neuron to the interval\[z¯j\(r\),z¯j\(r\)\]\[\\underline\{z\}^\{\(r\)\}\_\{j\},\\overline\{z\}^\{\(r\)\}\_\{j\}\]\.
### 4\.2\.Linear Relaxations of Bernstein Activations
The subsequent step necessitates the creation of certified linear over\- and under\-approximations for every Bernstein activation function\. For an isolated interval\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\], the primary secant line intersecting the initial and final control points of the activation curve defines a shared slope for both bounding lines\. By leveraging the intrinsic mathematical properties of the Bernstein coefficients, the precise vertical offsets required to guarantee bounding validity can be computed algebraically, thereby circumventing the computational overhead of nonlinear curve searches\. This is captured by the following result\.
###### Lemma 4\.1 \(Bernstein linear relaxation\)\.
Letc′c^\{\\prime\}be the Bernstein coefficients ofσj\(r\)\\sigma^\{\(r\)\}\_\{j\}on\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\], and lets∈ℝs\\in\\mathbb\{R\}be any slope\. Define:
ei\\displaystyle e\_\{i\}=ci′−sξi,ξi=z¯\+\(z¯−z¯\)i/n,i=0,…,n,\\displaystyle=c^\{\\prime\}\_\{i\}\-s\\,\\xi\_\{i\},\\quad\\xi\_\{i\}=\\underline\{z\}\+\(\\overline\{z\}\-\\underline\{z\}\)\\,i/n,\\quad i=0,\\dots,n,and letβ¯=miniei\\underline\{\\beta\}=\\min\_\{i\}e\_\{i\}andβ¯=maxiei\\overline\{\\beta\}=\\max\_\{i\}e\_\{i\}\. Then:
\(10\)sz\+β¯≤σj\(r\)\(z\)≤sz\+β¯for allz∈\[z¯,z¯\]\.s\\,z\+\\underline\{\\beta\}\\;\\leq\\;\\sigma^\{\(r\)\}\_\{j\}\(z\)\\;\\leq\\;s\\,z\+\\overline\{\\beta\}\\qquad\\text\{for all \}z\\in\[\\underline\{z\},\\overline\{z\}\]\.
According to the linear precision property \(Property P4\) of Bernstein polynomials, any affine mappingz↦szz\\mapsto szon the interval\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]is exactly represented byn\+1n\+1Bernstein coefficientssξis\\xi\_\{i\}\. Consequently, the termeie\_\{i\}quantifies the vertical displacement of theii\-th control point ofσj\(r\)\\sigma\_\{j\}^\{\(r\)\}relative to this linear approximation, effectively serving as theii\-th Bernstein coefficient of the residual functionσj\(r\)\(z\)−sz\\sigma\_\{j\}^\{\(r\)\}\(z\)\-sz\. The enclosure property \(Property P1\) ensures that the discrete extrema of these offsets strictly bound the continuous residual function over the defined interval, establishing mathematically sound offsets for the parallel relaxation lines\. TheBernBRSarchitecture utilizes the exact secant slopes=\(cn′−c0′\)/\(z¯−z¯\)s=\(c\_\{n\}^\{\\prime\}\-c\_\{0\}^\{\\prime\}\)/\(\\overline\{z\}\-\\underline\{z\}\), which yields a total relaxation width defined byβ=β¯−β¯\\beta=\\overline\{\\beta\}\-\\underline\{\\beta\}\.
While standard Bernstein coefficients reliably enclose non\-monotone activations, they may occasionally induce overly conservative geometric bounds \(as shown in Figure[3](https://arxiv.org/html/2611.22083#S4.F3)\)\. To mitigate this,BernBRSpartitions the input domain intoJ=2J=2equal sub\-intervals, extracting bounding offsets from their localized coefficients to formulate significantly tighter enclosures\. Although this localized refinement imposesJJadditional restrictions per neuron, these constraints cascade through the linear bounds to progressively tighten the reachable intervals of subsequent, deeper layers\. Ultimately, the maximum width of this relaxation is strictly upper\-bounded by a constant factor multiplied by the squared interval width \(Proposition[A\.3](https://arxiv.org/html/2611.22083#A1.Thmtheorem3)\)\.
ℓ′\\ell^\{\\prime\}u′u^\{\\prime\}J=1J=1β\\betaℓ′\\ell^\{\\prime\}u′u^\{\\prime\}J=2J=2βJ\\beta\_\{J\}Figure 3\.Relaxation of a non\-monotone activation of degree 5 with the secant slope\. Left: offsets from the control points on\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]\(J=1J=1\)\. Right: the same slope with offsets from two sub\-intervals \(J=2J=2\), which gives a smaller width\.
### 4\.3\.Linear Bounds on the Target Rows
Akin to the linear bound propagation used by tools like CROWN\([Zhang et al\., 2018](https://arxiv.org/html/2611.22083#bib.bib38);[Shi et al\., 2025](https://arxiv.org/html/2611.22083#bib.bib29)\), we map the linear relaxations localized at each neuron to compute the final network\-wise linear approximation\. To that end, the neuron\-wise linear bounds are systematically composed via back\-substitution—propagating from the target polyhedral constraints down to the input space—adapting the established principles of linear bound propagation\. This is captured by the following theorem\.
###### Theorem 4\.2 \(Linear bounds and gap identity\)\.
Let every neuronjjof every layerrrbe relaxed on an interval that containszj\(r\)\(x\)z^\{\(r\)\}\_\{j\}\(x\)for allx∈ℛ\(P\)x\\in\\mathcal\{R\}\(P\)\. Lets\(r\)s^\{\(r\)\},β¯\(r\)\\underline\{\\beta\}^\{\(r\)\}andβ¯\(r\)\\overline\{\\beta\}\{\}^\{\(r\)\}be the vectors of slopes, lower offsets and upper offsets of layerrr\. DefineΛ\(R\)=HWR\+1\\Lambda^\{\(R\)\}=HW\_\{R\+1\},oout=HbR\+1o\_\{\\mathrm\{out\}\}=Hb\_\{R\+1\}, and forr=R,…,1r=R,\\dots,1:
\(11\)Γ\(r\)=Λ\(r\)diag\(s\(r\)\),Λ\(r−1\)=Γ\(r\)Wr\.\\Gamma^\{\(r\)\}=\\Lambda^\{\(r\)\}\\operatorname\{diag\}\(s^\{\(r\)\}\),\\qquad\\Lambda^\{\(r\-1\)\}=\\Gamma^\{\(r\)\}W\_\{r\}\.LetA=Λ\(0\)∈ℝmH×dA=\\Lambda^\{\(0\)\}\\in\\mathbb\{R\}^\{m\_\{H\}\\times d\}, and letΛ\(r\)\+=max\(Λ\(r\),0\)\\Lambda^\{\(r\)\+\}=\\max\(\\Lambda^\{\(r\)\},0\)andΛ\(r\)−=min\(Λ\(r\),0\)\\Lambda^\{\(r\)\-\}=\\min\(\\Lambda^\{\(r\)\},0\)entry\-wise\. Define
\(12\)clo\\displaystyle c\_\{\\mathrm\{lo\}\}=oout\+∑r=1R\(Λ\(r\)\+β¯\(r\)\+Λ\(r\)−β¯\+\(r\)Γ\(r\)br\),\\displaystyle=o\_\{\\mathrm\{out\}\}\+\\sum\_\{r=1\}^\{R\}\\Big\(\\Lambda^\{\(r\)\+\}\\underline\{\\beta\}^\{\(r\)\}\+\\Lambda^\{\(r\)\-\}\\overline\{\\beta\}\{\}^\{\(r\)\}\+\\Gamma^\{\(r\)\}b\_\{r\}\\Big\),\(13\)cup\\displaystyle c\_\{\\mathrm\{up\}\}=oout\+∑r=1R\(Λ\(r\)\+β¯\+\(r\)Λ\(r\)−β¯\(r\)\+Γ\(r\)br\),\\displaystyle=o\_\{\\mathrm\{out\}\}\+\\sum\_\{r=1\}^\{R\}\\Big\(\\Lambda^\{\(r\)\+\}\\overline\{\\beta\}\{\}^\{\(r\)\}\+\\Lambda^\{\(r\)\-\}\\underline\{\\beta\}^\{\(r\)\}\+\\Gamma^\{\(r\)\}b\_\{r\}\\Big\),and the linear boundsL\(x\)=Ax\+cloL\(x\)=Ax\+c\_\{\\mathrm\{lo\}\}andU\(x\)=Ax\+cupU\(x\)=Ax\+c\_\{\\mathrm\{up\}\}\. Then for everyx∈ℛ\(P\)x\\in\\mathcal\{R\}\(P\):
\(14\)L\(x\)≤Hf\(x\)≤U\(x\)andU\(x\)−L\(x\)=∑r=1R\|Λ\(r\)\|β\(r\),L\(x\)\\leq Hf\(x\)\\leq U\(x\)\\quad\\text\{and\}\\quad U\(x\)\-L\(x\)=\\sum\_\{r=1\}^\{R\}\|\\Lambda^\{\(r\)\}\|\\,\\beta^\{\(r\)\},where\|Λ\(r\)\|\|\\Lambda^\{\(r\)\}\|is the entry\-wise absolute value andβ\(r\)=β¯\(r\)−β¯\(r\)\\beta^\{\(r\)\}=\\overline\{\\beta\}\{\}^\{\(r\)\}\-\\underline\{\\beta\}^\{\(r\)\}is the vector of relaxation widths of layerrr\. The*gap of rowii*is theii\-th entryδi\\delta\_\{i\}ofU\(x\)−L\(x\)U\(x\)\-L\(x\)\.
While Theorem[4\.2](https://arxiv.org/html/2611.22083#S4.Thmtheorem2)formulates continuous bounding functions of the input statexx, definitively resolving a discrete activation pattern necessitates absolute numerical upper and lower bounds for each target row evaluated over the regionℛ\(P\)\\mathcal\{R\}\(P\)\. The recursive back\-substitution process yields partial linear bounds parameterized in terms of intermediate states,σ\(r\)\(z\(r\)\)\\sigma^\{\(r\)\}\(z^\{\(r\)\}\)orz\(r\)z^\{\(r\)\}, at every intermediate layer, culminating in the explicit input\-space boundsLLandUU\. Because the extreme values of each partial layer\-wise bound remain mathematically valid across the entire regionℛ\(P\)\\mathcal\{R\}\(P\),BernBRSsystematically isolates and retains the tightest observed extrema across all computational layers\. These optimally tight extrema constitute the final row bounds\[ρ¯,ρ¯\]\[\\underline\{\\rho\},\\overline\{\\rho\}\], which are ultimately responsible for either mathematically pruning or validating the activation pattern\. The integration of intermediate deep\-layer constraints is critical, as split limits imposed on deeper neurons systematically tighten the bounds solely via localized interval restrictions\. By recursively applying this identical bounding procedure to the network weightsWrW\_\{r\}and biasesbrb\_\{r\}for layersr≥2r\\geq 2, the algorithm tightens the localized pre\-activation intervals\[z¯\(r\),z¯\(r\)\]\[\\underline\{z\}^\{\(r\)\},\\overline\{z\}^\{\(r\)\}\]immediately prior to applying the linear relaxation at layerrr\.
Algorithm 3Certified bounds overℛ\(P\)\\mathcal\{R\}\(P\)\(forward bounding\)1:Pattern
P=\(X^,Z^\)P=\(\\hat\{X\},\\hat\{Z\}\)
2:Interval bounds
ℬP\\mathcal\{B\}\_\{P\}, linear bounds
\(A,clo,cup\)\(A,c\_\{\\mathrm\{lo\}\},c\_\{\\mathrm\{up\}\}\), row bounds
\[ρ¯,ρ¯\]\[\\underline\{\\rho\},\\overline\{\\rho\}\], coefficients
Λ\(r\)\\Lambda^\{\(r\)\}, relaxation widths
β\(r\)\\beta^\{\(r\)\}
3:Interval bounds of every layer by Lemma[A\.1](https://arxiv.org/html/2611.22083#A1.Thmtheorem1);ifsome interval is emptyreturnempty
4:for
r=1,…,Rr=1,\\dots,Rdo
5:if
r≥2r\\geq 2thenintersect
\[z¯\(r\),z¯\(r\)\]\[\\underline\{z\}^\{\(r\)\},\\overline\{z\}^\{\(r\)\}\]with the bounds from the rows of
WrW\_\{r\}; recompute
\[σ¯\(r\),σ¯\(r\)\]\[\\underline\{\\sigma\}^\{\(r\)\},\\overline\{\\sigma\}^\{\(r\)\}\]and the certificates
6:endif
7:Relax every neuron of layer
rr\(Lemma[4\.1](https://arxiv.org/html/2611.22083#S4.Thmtheorem1), secant slope\)
8:endfor
9:Back\-substitute the target rows \(Theorem[4\.2](https://arxiv.org/html/2611.22083#S4.Thmtheorem2)\); compute the row bounds
10:returnall bounds
## 5\.Backward Contraction
This section formalizes the theoretical foundations of the backward contraction methodology introduced in Section[3](https://arxiv.org/html/2611.22083#S3)with the corresponding proofs provided in Appendix[B](https://arxiv.org/html/2611.22083#A2)\.
### 5\.1\.Backward Contraction over One Layer
Our algorithm executes the interval bound propagation in reverse across a single network layer\. This operation requires the forward bounds\[σ¯,σ¯\]\[\\underline\{\\sigma\},\\overline\{\\sigma\}\]of the incoming post\-activations and the backward bounds\[z¯′,z¯′\]\[\\underline\{z\}^\{\\prime\},\\overline\{z\}^\{\\prime\}\]of the outgoing pre\-activations as inputs to yield the refined backward bounds\[σ¯′,σ¯′\]\[\\underline\{\\sigma\}^\{\\prime\},\\overline\{\\sigma\}^\{\\prime\}\]of the entering post\-activations\. For any hidden layerrr, the affine mapping is defined asz=Wσ\+bz=W\\sigma\+b, whereW=WrW=W\_\{r\},b=brb=b\_\{r\}, andσ=σ\(r−1\)\(z\(r−1\)\)\\sigma=\\sigma^\{\(r\-1\)\}\(z^\{\(r\-1\)\}\)\. At the output layer, the target constraintHWR\+1σ\(R\)\(z\(R\)\)\+HbR\+1≤hHW\_\{R\+1\}\\sigma^\{\(R\)\}\(z^\{\(R\)\}\)\+Hb\_\{R\+1\}\\leq hnecessitates substitutingW=HWR\+1W=HW\_\{R\+1\},b=HbR\+1b=Hb\_\{R\+1\}, andσ=σ\(R\)\(z\(R\)\)\\sigma=\\sigma^\{\(R\)\}\(z^\{\(R\)\}\)\. Consequently, the output backward bounds are constrained solely by upper limits defined byhh, completely lack lower limits, and rely entirely on exact network weights rather than geometric relaxations\. The next lemma captures these computations and establishes the correctness of our approach\.
###### Lemma 5\.1 \(Backward interval propagation over one layer\)\.
Letσ∈\[σ¯,σ¯\]\\sigma\\in\[\\underline\{\\sigma\},\\overline\{\\sigma\}\]andz=Wσ\+b∈\[z¯′,z¯′\]z=W\\sigma\+b\\in\[\\underline\{z\}^\{\\prime\},\\overline\{z\}^\{\\prime\}\]\. For every rowjjand everykkwithWjk≠0W\_\{jk\}\\neq 0,
Wjkσk∈\[\\displaystyle W\_\{jk\}\\,\\sigma\_\{k\}\\in\\Big\[\\,z¯j′−bj−∑k′≠k\(Wjk′\+σ¯k′\+Wjk′−σ¯k′\),\\displaystyle\\underline\{z\}^\{\\prime\}\_\{j\}\-b\_\{j\}\-\\sum\_\{k^\{\\prime\}\\neq k\}\\big\(W^\{\+\}\_\{jk^\{\\prime\}\}\\,\\overline\{\\sigma\}\_\{k^\{\\prime\}\}\+W^\{\-\}\_\{jk^\{\\prime\}\}\\,\\underline\{\\sigma\}\_\{k^\{\\prime\}\}\\big\),z¯j′−bj−∑k′≠k\(Wjk′\+σ¯k′\+Wjk′−σ¯k′\)\],\\displaystyle\\overline\{z\}^\{\\prime\}\_\{j\}\-b\_\{j\}\-\\sum\_\{k^\{\\prime\}\\neq k\}\\big\(W^\{\+\}\_\{jk^\{\\prime\}\}\\,\\underline\{\\sigma\}\_\{k^\{\\prime\}\}\+W^\{\-\}\_\{jk^\{\\prime\}\}\\,\\overline\{\\sigma\}\_\{k^\{\\prime\}\}\\big\)\\Big\],where the two sums are the largest and the smallest value of the other terms of rowjj, as in \([8](https://arxiv.org/html/2611.22083#S4.E8)\)\.
By isolatingσk\\sigma\_\{k\}and dividing by the weightWjkW\_\{jk\}, one obtains an updated operational interval forσk\\sigma\_\{k\}, wherein the interval endpoints are strictly inverted ifWjk<0W\_\{jk\}<0\. The final backward bound\[σ¯k′,σ¯k′\]\[\\underline\{\\sigma\}\_\{k\}^\{\\prime\},\\overline\{\\sigma\}\_\{k\}^\{\\prime\}\]is established by intersecting these row\-wise intervals across all rowsjjwith the existing forward bound\[σ¯k,σ¯k\]\[\\underline\{\\sigma\}\_\{k\},\\overline\{\\sigma\}\_\{k\}\], ensuring that the true activationσk\\sigma\_\{k\}is rigorously confined within this intersection\. If a bound in\[z¯j′,z¯j′\]\[\\underline\{z\}\_\{j\}^\{\\prime\},\\overline\{z\}\_\{j\}^\{\\prime\}\]lacks a finite endpoint, it mathematically imposes no constraint from that corresponding direction\. Furthermore, an empty intersection definitively proves that no feasibleσ\\sigmaexists to satisfy the given constraints\.
### 5\.2\.Backward Contraction for Monotone Activation Patterns
For the special case when the activation function is certified monotone \(Lemma[B\.1](https://arxiv.org/html/2611.22083#A2.Thmtheorem1)provides the sufficient conditions to check if an activation is monotone\), one can compute tighter bounds by exploiting such monotonicity as follows\. The newly computed backward bound\[σ¯′,σ¯′\]\[\\underline\{\\sigma\}^\{\\prime\},\\overline\{\\sigma\}^\{\\prime\}\]of a post\-activation is compared directly against its corresponding forward bound\. Endpoints that fail to provide tighter constraints leave the corresponding pre\-activation boundaries entirely unaltered\. Conversely, a tighter endpoint signifies a function crossing strictly within the domain\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\], which the BERNBRS framework dynamically isolates using a fixed\-iteration bisection method \(configured to 60 halvings in empirical evaluations\)\. By retaining the outer boundary of the terminal bisection bracket, the algorithm guarantees that the contracted pre\-activation bound\[z¯′,z¯′\]\[\\underline\{z\}^\{\\prime\},\\overline\{z\}^\{\\prime\}\]remains structurally conservative—potentially wider than the exact pre\-image, but strictly never narrower as captured by the following result\.
###### Lemma 5\.2 \(Inverse of a certified monotone activation\)\.
Letσ=σj\(r\)\\sigma=\\sigma^\{\(r\)\}\_\{j\}be certified non\-decreasing on the interval\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]\(item 2 of Lemma[B\.1](https://arxiv.org/html/2611.22083#A2.Thmtheorem1)\), and let\[σ¯′,σ¯′\]\[\\underline\{\\sigma\}^\{\\prime\},\\overline\{\\sigma\}^\{\\prime\}\]be the allowed post\-activation interval\. Define the*contracted inverse interval*\[z¯′,z¯′\]\[\\underline\{z\}^\{\\prime\},\\overline\{z\}^\{\\prime\}\]as follows\.
1. \(1\)*Empty\.*Ifσ\(z¯\)<σ¯′\\sigma\(\\overline\{z\}\)<\\underline\{\\sigma\}^\{\\prime\}orσ\(z¯\)\>σ¯′\\sigma\(\\underline\{z\}\)\>\\overline\{\\sigma\}^\{\\prime\}, the output is empty\.
2. \(2\)*Lower end\.*Ifσ\(z¯\)≥σ¯′\\sigma\(\\underline\{z\}\)\\geq\\underline\{\\sigma\}^\{\\prime\}, thenz¯′=z¯\\underline\{z\}^\{\\prime\}=\\underline\{z\}\. Otherwise, start from\[a,b\]=\[z¯,z¯\]\[a,b\]=\[\\underline\{z\},\\overline\{z\}\], for whichσ\(a\)<σ¯′≤σ\(b\)\\sigma\(a\)<\\underline\{\\sigma\}^\{\\prime\}\\leq\\sigma\(b\)\. Replace\[a,b\]\[a,b\]a fixed number of times by the half that keeps this property\. Thenz¯′=a\\underline\{z\}^\{\\prime\}=a\.
3. \(3\)*Upper end\.*Ifσ\(z¯\)≤σ¯′\\sigma\(\\overline\{z\}\)\\leq\\overline\{\\sigma\}^\{\\prime\}, thenz¯′=z¯\\overline\{z\}^\{\\prime\}=\\overline\{z\}\. Otherwise, halve\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]in the same way, keepingσ\(a\)≤σ¯′<σ\(b\)\\sigma\(a\)\\leq\\overline\{\\sigma\}^\{\\prime\}<\\sigma\(b\)\. Thenz¯′=b\\overline\{z\}^\{\\prime\}=b\.
Then\[z¯′,z¯′\]⊆\[z¯,z¯\]\[\\underline\{z\}^\{\\prime\},\\overline\{z\}^\{\\prime\}\]\\subseteq\[\\underline\{z\},\\overline\{z\}\]contains everyz∈\[z¯,z¯\]z\\in\[\\underline\{z\},\\overline\{z\}\]withσ\(z\)∈\[σ¯′,σ¯′\]\\sigma\(z\)\\in\[\\underline\{\\sigma\}^\{\\prime\},\\overline\{\\sigma\}^\{\\prime\}\]\. An empty output means that no suchzzexists\. Each halving divides the width of the bracket\[a,b\]\[a,b\], which bounds the distance of a moved end to the exact crossing, by two\. For a certified non\-increasing neuron, apply the lemma to−σ\-\\sigmaand\[−σ¯′,−σ¯′\]\[\-\\overline\{\\sigma\}^\{\\prime\},\-\\underline\{\\sigma\}^\{\\prime\}\]\.
### 5\.3\.Soundness of Backward Contraction
Algorithm[4](https://arxiv.org/html/2611.22083#alg4)synthesizes these backward propagation and inversion procedures into a unified process\. Specifically, line 7 leverages the lower linear bound derived in Theorem[4\.2](https://arxiv.org/html/2611.22083#S4.Thmtheorem2), which is mathematically validated across the entire spatial regionℛ\(P\)\\mathcal\{R\}\(P\)\.
Algorithm 4Backward contraction of a pattern1:Pattern
PP; its bounds
ℬP\\mathcal\{B\}\_\{P\}with intervals
\[z¯\(r\),z¯\(r\)\]\[\\underline\{z\}^\{\(r\)\},\\overline\{z\}^\{\(r\)\}\],
\[σ¯\(r\),σ¯\(r\)\]\[\\underline\{\\sigma\}^\{\(r\)\},\\overline\{\\sigma\}^\{\(r\)\}\]and monotonicity certificates; the linear lower bound
Ax\+cloAx\+c\_\{\\mathrm\{lo\}\}of Theorem[4\.2](https://arxiv.org/html/2611.22083#S4.Thmtheorem2)
2:Contracted pattern
P′P^\{\\prime\}, orempty
3:Contract
\[σ¯\(R\),σ¯\(R\)\]\[\\underline\{\\sigma\}^\{\(R\)\},\\overline\{\\sigma\}^\{\(R\)\}\]to
\[σ¯′\(R\),σ¯′\(R\)\]\[\\underline\{\\sigma\}^\{\\prime\(R\)\},\\overline\{\\sigma\}^\{\\prime\(R\)\}\]with
HWR\+1σ\(R\)\(z\(R\)\)\+HbR\+1≤hHW\_\{R\+1\}\\sigma^\{\(R\)\}\(z^\{\(R\)\}\)\+Hb\_\{R\+1\}\\leq h⊳\\trianglerightLemma[5\.1](https://arxiv.org/html/2611.22083#S5.Thmtheorem1)
4:for
r=R,…,1r=R,\\dots,1do
5:For every certified monotone neuron:
\[z¯j′\(r\),z¯j′\(r\)\]←\[\\underline\{z\}^\{\\prime\(r\)\}\_\{j\},\\overline\{z\}^\{\\prime\(r\)\}\_\{j\}\]\\leftarrowthe contracted inverse interval for
\[σ¯j′\(r\),σ¯j′\(r\)\]\[\\underline\{\\sigma\}^\{\\prime\(r\)\}\_\{j\},\\overline\{\\sigma\}^\{\\prime\(r\)\}\_\{j\}\]; other neurons keep
\[z¯j\(r\),z¯j\(r\)\]\[\\underline\{z\}^\{\(r\)\}\_\{j\},\\overline\{z\}^\{\(r\)\}\_\{j\}\]⊳\\trianglerightLemma[5\.2](https://arxiv.org/html/2611.22083#S5.Thmtheorem2)
6:Contract
\[σ¯\(r−1\),σ¯\(r−1\)\]\[\\underline\{\\sigma\}^\{\(r\-1\)\},\\overline\{\\sigma\}^\{\(r\-1\)\}\]to
\[σ¯′\(r−1\),σ¯′\(r−1\)\]\[\\underline\{\\sigma\}^\{\\prime\(r\-1\)\},\\overline\{\\sigma\}^\{\\prime\(r\-1\)\}\]with
z¯′\(r\)≤Wrσ\(r−1\)\(z\(r−1\)\)\+br≤z¯′\(r\)\\underline\{z\}^\{\\prime\(r\)\}\\leq W\_\{r\}\\sigma^\{\(r\-1\)\}\(z^\{\(r\-1\)\}\)\+b\_\{r\}\\leq\\overline\{z\}^\{\\prime\(r\)\}⊳\\trianglerightLemma[5\.1](https://arxiv.org/html/2611.22083#S5.Thmtheorem1);σ\(0\)\(z\(0\)\)=x\\sigma^\{\(0\)\}\(z^\{\(0\)\}\)=x
7:ifsome interval is emptyreturnempty
8:endfor
9:Contract
\[σ¯′\(0\),σ¯′\(0\)\]\[\\underline\{\\sigma\}^\{\\prime\(0\)\},\\overline\{\\sigma\}^\{\\prime\(0\)\}\]with
Ax\+clo≤hAx\+c\_\{\\mathrm\{lo\}\}\\leq h;ifemptyreturnempty⊳\\trianglerightLemma[5\.1](https://arxiv.org/html/2611.22083#S5.Thmtheorem1), Theorem[4\.2](https://arxiv.org/html/2611.22083#S4.Thmtheorem2)
10:return
P′P^\{\\prime\}with box
X^′=\[σ¯′\(0\),σ¯′\(0\)\]\\hat\{X\}^\{\\prime\}=\[\\underline\{\\sigma\}^\{\\prime\(0\)\},\\overline\{\\sigma\}^\{\\prime\(0\)\}\]and intervals
Z^′\(r\)=Z^\(r\)∩\[z¯′\(r\),z¯′\(r\)\]\\hat\{Z\}^\{\\prime\(r\)\}=\\hat\{Z\}^\{\(r\)\}\\cap\[\\underline\{z\}^\{\\prime\(r\)\},\\overline\{z\}^\{\\prime\(r\)\}\]
###### Theorem 5\.3 \(Soundness of contraction\)\.
LetP′P^\{\\prime\}be returned by Algorithm[4](https://arxiv.org/html/2611.22083#alg4)\. Thenℛ\(P\)∩BRSf\(𝒴\)⊆ℛ\(P′\)⊆ℛ\(P\)\\mathcal\{R\}\(P\)\\cap\\BRS\_\{f\}\(\\mathcal\{Y\}\)\\subseteq\\mathcal\{R\}\(P^\{\\prime\}\)\\subseteq\\mathcal\{R\}\(P\)\. If the algorithm returnsempty, thenℛ\(P\)∩BRSf\(𝒴\)=∅\\mathcal\{R\}\(P\)\\cap\\BRS\_\{f\}\(\\mathcal\{Y\}\)=\\emptyset\.
In other words, the iterative contraction sequence delineated in Algorithm[2](https://arxiv.org/html/2611.22083#alg2)preserves mathematical soundness as shown in Theorem[5\.3](https://arxiv.org/html/2611.22083#S5.Thmtheorem3), ensuring the recursively composed mapping remains strictly certified\. The bounding limitsLL,UU, and\[ρ¯,ρ¯\]\[\\underline\{\\rho\},\\overline\{\\rho\}\]calculated during the terminal bounding pass inherently apply to the established geometric region of that specific pass, and by necessary extension, safely enclose the final contracted subspace\. These established limits systematically dictate the final analytical classification of the pattern\.
### 5\.4\.Geometric Approximations and Polytope Verification
The last step is to classify the activation patternPP, based on the contracted patternP′P^\{\\prime\}, into those that need more processing \(undecided regions\), those who are part of the inner BRS, and those that are part of the outer BRS\. The following result provide the conditions needed for such classification\.
###### Theorem 5\.4 \(Classification of Activation Patterns\)\.
LetℬP\\mathcal\{B\}\_\{P\},LL,UU,\[ρ¯,ρ¯\]\[\\underline\{\\rho\},\\overline\{\\rho\}\]be the bounds of forward bounding forPP\.
1. \(1\)*Prune\.*IfℬP\\mathcal\{B\}\_\{P\}is empty, orρ¯i\>hi\\underline\{\\rho\}\_\{i\}\>h\_\{i\}for some rowii, thenℛ\(P\)∩BRSf\(𝒴\)=∅\\mathcal\{R\}\(P\)\\cap\\BRS\_\{f\}\(\\mathcal\{Y\}\)=\\emptyset\.
2. \(2\)*Accept\.*Ifρ¯i≤hi\\overline\{\\rho\}\_\{i\}\\leq h\_\{i\}for every rowii, thenℛ\(P\)⊆BRSf\(𝒴\)\\mathcal\{R\}\(P\)\\subseteq\\BRS\_\{f\}\(\\mathcal\{Y\}\)\.
3. \(3\)*Inner part\.*I\(P\)=ℛ\(P\)∩\{x:U\(x\)≤h\}⊆BRSf\(𝒴\)I\(P\)=\\mathcal\{R\}\(P\)\\cap\\\{x:U\(x\)\\leq h\\\}\\subseteq\\BRS\_\{f\}\(\\mathcal\{Y\}\)\.
4. \(4\)*Outer part\.*O\(P\)=ℛ\(P\)∩\{x:L\(x\)≤h\}⊇ℛ\(P\)∩BRSf\(𝒴\)O\(P\)=\\mathcal\{R\}\(P\)\\cap\\\{x:L\(x\)\\leq h\\\}\\supseteq\\mathcal\{R\}\(P\)\\cap\\BRS\_\{f\}\(\\mathcal\{Y\}\), andO\(P\)O\(P\)lies in the polytope: O^\(P\)=\{x∈X^:z¯^\(1\)≤W1x\+b1≤z^¯\(1\),Ax\+clo≤h\}\.\\hat\{O\}\(P\)=\\big\\\{x\\in\\hat\{X\}:\\underline\{\\hat\{z\}\}^\{\(1\)\}\\leq W\_\{1\}x\+b\_\{1\}\\leq\\overline\{\\hat\{z\}\}^\{\(1\)\},\\;Ax\+c\_\{\\mathrm\{lo\}\}\\leq h\\big\\\}\.
Every finalized subset allocated to collectionsIIandOOadheres to the rigorous structural prerequisites of Problem 1, formulated as a pattern region intersected withmHm\_\{H\}specific halfspaces\. The outer approximations can be efficiently mapped and stored as closed polytopesO^\(P\)\\hat\{O\}\(P\)\. Upon certifying a pattern as fully accepted, theBernBRSframework executes an accelerated forward bounding pass that explicitly omits the interval constraints for layersr≥2r\\geq 2\. If this unconstrained analytical pass verifies that all target rows remain definitively satisfied, the algorithm formalizes the accepted region as an encompassing polytope\. This final structural polytope completely encapsulates the original sub\-domainℛ\(P\)\\mathcal\{R\}\(P\)and, according to item 2 evaluated over the relaxed pattern, is strictly proven to reside withinBRSf\(𝒴\)BRS\_\{f\}\(\\mathcal\{Y\}\)\.
## 6\.Branching
This section gives the rule of branching for an undecided contracted patternP′P^\{\\prime\}with boxX^′\\hat\{X\}^\{\\prime\}and an outer polytopeO^\(P′\)\\hat\{O\}\(P^\{\\prime\}\)\(Theorem[5\.4](https://arxiv.org/html/2611.22083#S5.Thmtheorem4)\)\. Appendix[C](https://arxiv.org/html/2611.22083#A3)gives the proofs and the supporting statements\.
### 6\.1\.Candidate and Gap Decomposition
The first step of splitting is to find the target row with the largest gap between its bounds\. To decide which rows are ambiguous, we start with the centre point ofX^′\\hat\{X\}^\{\\prime\}\. It is taken and projected in up to3030projection steps onto the violated halfspaces ofO^\(P′\)\\hat\{O\}\(P^\{\\prime\}\)\. Then it is clipped to the box after each step\. The result is the candidate pointx⋆x^\{\\star\}that is used to select the rows\. A row is called ambiguous atx⋆x^\{\\star\}ifLi\(x⋆\)≤hi<Ui\(x⋆\)L\_\{i\}\(x^\{\\star\}\)\\leq h\_\{i\}<U\_\{i\}\(x^\{\\star\}\)\. The deciding rowi⋆i^\{\\star\}is the ambiguous row with the largest gapδi=Ui−Li\\delta\_\{i\}=U\_\{i\}\-L\_\{i\}\. If no row is ambiguous,i⋆i^\{\\star\}is the row with the largest gap among the rows whose upper row boundρ¯i\\overline\{\\rho\}\_\{i\}exceedshih\_\{i\}\.
After choosingi⋆i^\{\\star\},BernBRSrecords the contribution of each neuron to its gap\. By the gap identity \([14](https://arxiv.org/html/2611.22083#S4.E14)\), the contribution of neuron\(r,j\)\(r,j\)isθrj=\|Λi⋆j\(r\)\|βj\(r\)\\theta\_\{rj\}=\|\\Lambda^\{\(r\)\}\_\{i^\{\\star\}j\}\|\\,\\beta^\{\(r\)\}\_\{j\}, the sensitivity of the target row gap to the neuron times the relaxation width of the neuron\. These contributions sum to the target gapδi⋆\\delta\_\{i^\{\\star\}\}\.
### 6\.2\.Split Selection
Halving the interval of neuron\(r,j\)\(r,j\)divides its relaxation widthβj\(r\)\\beta^\{\(r\)\}\_\{j\}by about four \(Proposition[A\.3](https://arxiv.org/html/2611.22083#A1.Thmtheorem3)\), so the reduction of the neuron’s share of the target gap is about34θrj\\tfrac\{3\}\{4\}\\theta\_\{rj\}, which is the neuron score\. Halving input dimensioniiofX^′\\hat\{X\}^\{\\prime\}reduces the target gap through every neuron\. It shrinks the interval width ofzj\(r\)z^\{\(r\)\}\_\{j\}by about the factor1−Sji\(r\)/21\-S^\{\(r\)\}\_\{ji\}/2, whereSji\(r\)S^\{\(r\)\}\_\{ji\}is the share of that width due toxix\_\{i\}\(Appendix[C\.1](https://arxiv.org/html/2611.22083#A3.SS1)\)\. The relaxation width then shrinks by about the factor\(1−Sji\(r\)/2\)2\(1\-S^\{\(r\)\}\_\{ji\}/2\)^\{2\}, so the neuron’s share of the target gap falls by aboutθrj\(1−\(1−Sji\(r\)/2\)2\)\\theta\_\{rj\}\\big\(1\-\(1\-S^\{\(r\)\}\_\{ji\}/2\)^\{2\}\\big\)\. The sum of these reductions over all neurons is the input score of dimensionii\.BernBRScompares the largest neuron score with the largest input score and splits the better option \(Algorithm[5](https://arxiv.org/html/2611.22083#alg5)\)\. For each neuron, the shares of all input dimensions sum to one, so each share is of order1/d1/dfor dense weights\. An input split therefore tends to win in low dimension, and a neuron split in high dimension\. No parameter of the rule depends ondd\.
Algorithm 5Refine\(P′,L,U\)\\textsc\{Refine\}\(P^\{\\prime\},L,U\)\(branching\)1:Undecided contracted pattern
P′P^\{\\prime\}, linear bounds with coefficients
Λ\(r\)\\Lambda^\{\(r\)\}and relaxation widths
β\(r\)\\beta^\{\(r\)\}
2:Children whose regions cover
ℛ\(P′\)\\mathcal\{R\}\(P^\{\\prime\}\), with estimated volumes, or
∅\\emptyset
3:
x⋆←x^\{\\star\}\\leftarrowprojection steps from the box centre onto
O^\(P′\)\\hat\{O\}\(P^\{\\prime\}\)
4:
i⋆←i^\{\\star\}\\leftarrowdeciding row at
x⋆x^\{\\star\};
θrj←\|Λi⋆j\(r\)\|βj\(r\)\\theta\_\{rj\}\\leftarrow\|\\Lambda^\{\(r\)\}\_\{i^\{\\star\}j\}\|\\beta^\{\(r\)\}\_\{j\}for all neurons \([14](https://arxiv.org/html/2611.22083#S4.E14)\)
5:
\(r,j\)←argmax34θrj\(r,j\)\\leftarrow\\arg\\max\\tfrac\{3\}\{4\}\\theta\_\{rj\};
i←argmax∑r,jiθrj\(1−\(1−Sji\(r\)/2\)2\)i\\leftarrow\\arg\\max\_\{i\}\\sum\_\{r,j\}\\theta\_\{rj\}\(1\-\(1\-S^\{\(r\)\}\_\{ji\}/2\)^\{2\}\)
6:Draw
MMuniform samples of
X^′\\hat\{X\}^\{\\prime\}and keep the
ninn\_\{\\mathrm\{in\}\}samples that lie in
ℛ\(P′\)\\mathcal\{R\}\(P^\{\\prime\}\)⊳\\trianglerightSection[6\.3](https://arxiv.org/html/2611.22083#S6.SS3)
7:ifthe input score of
iiexceeds the neuron score of
\(r,j\)\(r,j\)then
8:
C←C\\leftarrowthe two halves of
X^′\\hat\{X\}^\{\\prime\}along
ii
9:elseifthe set
SSof Section[6\.3](https://arxiv.org/html/2611.22083#S6.SS3)is non\-emptythen
10:
C←C\\leftarrowthe at most
2\|S\|\+12\|S\|\+1children of the joint split \([15](https://arxiv.org/html/2611.22083#S6.E15)\)
11:else
12:
C←C\\leftarrowthe split of
Z^j\(r\)\\hat\{Z\}^\{\(r\)\}\_\{j\}at the critical point closest to its midpoint, else at the midpoint
13:endif
14:Attach to each child its estimated volume \([18](https://arxiv.org/html/2611.22083#A3.E18)\);return
CC
Figure 4\.True BRS and sets computed byBernBRSon six random two\-input networks\. The top row shows the true BRS\. The bottom row shows the inner set, the undecided set and the true boundary on the same grid of400×400400\\times 400points\. Under each lower panel are the number of activation patterns, the inner and outer ratios, and the seconds of that run on one CPU core\.If the neuron wins and the setSSof Section[6\.3](https://arxiv.org/html/2611.22083#S6.SS3)is empty, Algorithm[5](https://arxiv.org/html/2611.22083#alg5)splits the best neuron at the candidate closest to the midpoint of\(z¯,z¯\)\(\\underline\{z\},\\overline\{z\}\), or at the midpoint if there is none\. The candidates are the real roots of\(σj\(r\)\)′\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\}in the interval if the neuron is not certified monotone\. On a fine enough subdivision at these points, the monotonicity certificate holds on every piece \(Proposition[C\.1](https://arxiv.org/html/2611.22083#A3.Thmtheorem1)\)\. Intervals narrower than10−910^\{\-9\}are never split, and the depth is limited toD=100,000D=100\{,\}000\.
### 6\.3\.Joint Splitting
The joint split rests on the concentration of the pre\-activations\. A pre\-activation interval is as wide as the sum of the weight magnitudes, while the pre\-activations of almost all inputs lie within a few standard deviations of their mean, and the standard deviation is smaller than the width by a factor between12\\sqrt\{12\}and12d\\sqrt\{12d\}\(Proposition[C\.2](https://arxiv.org/html/2611.22083#A3.Thmtheorem2)\)\. A bisection of such an interval halves it only and leaves almost all of the volume in one child\. Restricting the neuron to the narrow part shrinks its interval far more and moves almost no volume into the two tails\.
The narrow part is found from samples\. Algorithm[5](https://arxiv.org/html/2611.22083#alg5)drawsMMuniform samples ofX^′\\hat\{X\}^\{\\prime\}and keeps those that lie inℛ\(P′\)\\mathcal\{R\}\(P^\{\\prime\}\), at least1616of them\. For a neuron, the meanμ\\muand the standard deviationς\\varsigmaof its pre\-activation over these samples define its*central interval*\[μ−κς,μ\+κς\]∩\[z¯,z¯\]\[\\mu\-\\kappa\\varsigma,\\mu\+\\kappa\\varsigma\]\\cap\[\\underline\{z\},\\overline\{z\}\]\. The neuron is*eligible*if this interval is narrower thanω\(z¯−z¯\)\\omega\(\\overline\{z\}\-\\underline\{z\}\)\. We useκ=4\\kappa=4andω=1/2\\omega=1/2\.
The neurons to restrict come from the ranking of Section[6\.2](https://arxiv.org/html/2611.22083#S6.SS2)\. Sorted by score34θrj\\tfrac\{3\}\{4\}\\theta\_\{rj\}, decreasing, the shortest prefix whose scores sum to at leastφ=0\.8\\varphi=0\.8times the total is selected, and its eligible neurons\(r1,j1\),…,\(r\|S\|,j\|S\|\)\(r\_\{1\},j\_\{1\}\),\\dots,\(r\_\{\|S\|\},j\_\{\|S\|\}\)form the setSS, in that order\.
LetCt=\[c¯t,c¯t\]C\_\{t\}=\[\\underline\{c\}\_\{t\},\\overline\{c\}\_\{t\}\]be the central interval andztz\_\{t\}the pre\-activation of thett\-th neuron\. The joint split nests the restrictions\. The first neuron gives two tail children\. With the first neuron held in its central interval, the second neuron gives two more, and so on\. The last child holds every neuron ofSSin its central interval\. The children ofP′P^\{\\prime\}are
\(15\)Tt−\\displaystyle T\_\{t\}^\{\-\}=ℛ\(P′\)∩\{zs∈Cs,s<t\}∩\{zt≤c¯t\},\\displaystyle=\\mathcal\{R\}\(P^\{\\prime\}\)\\cap\\\{z\_\{s\}\\in C\_\{s\},\\ s<t\\\}\\cap\\\{z\_\{t\}\\leq\\underline\{c\}\_\{t\}\\\},Tt\+\\displaystyle T\_\{t\}^\{\+\}=ℛ\(P′\)∩\{zs∈Cs,s<t\}∩\{zt≥c¯t\},\\displaystyle=\\mathcal\{R\}\(P^\{\\prime\}\)\\cap\\\{z\_\{s\}\\in C\_\{s\},\\ s<t\\\}\\cap\\\{z\_\{t\}\\geq\\overline\{c\}\_\{t\}\\\},K\\displaystyle K=ℛ\(P′\)∩\{zs∈Cs,s=1,…,\|S\|\}\.\\displaystyle=\\mathcal\{R\}\(P^\{\\prime\}\)\\cap\\\{z\_\{s\}\\in C\_\{s\},\\ s=1,\\dots,\|S\|\\\}\.HereTt±T\_\{t\}^\{\\pm\},t=1,…,\|S\|t=1,\\dots,\|S\|, are the tails of thett\-th neuron andKKis the central child\. These at most2\|S\|\+12\|S\|\+1children coverℛ\(P′\)\\mathcal\{R\}\(P^\{\\prime\}\)\(Lemma[C\.3](https://arxiv.org/html/2611.22083#A3.Thmtheorem3)\)\. An input ofℛ\(P′\)\\mathcal\{R\}\(P^\{\\prime\}\)either has everyztz\_\{t\}inCtC\_\{t\}and lies inKK, or it has a first neuronttwithztz\_\{t\}outsideCtC\_\{t\}and lies inTt−T\_\{t\}^\{\-\}orTt\+T\_\{t\}^\{\+\}\. Each child carries an estimated volume, which only orders the priority queue\. A tail receives aboutη=Φ\(−κ\)≈3⋅10−5\\eta=\\Phi\(\-\\kappa\)\\approx 3\\cdot 10^\{\-5\}of its parent \(Appendix[C\.3](https://arxiv.org/html/2611.22083#A3.SS3)\)\. The joint split spends one processed pattern and one round on the whole set\.
## 7\.Experiments
We evaluate the proposedBernBRSframework through two foundational experiments and two applied case studies\. The first experiment assesses the algorithmic correctness of the framework on randomized two\-input networks\. The second experiment investigates the framework’s scalability when applied to image classifiers containing up to 2\.3 million parameters\. The first case study examines a hybrid dynamical system, specifically a legged robot operating in a closed loop\. The second case study evaluates a distilled transformer block based on the TinyBERT architecture\. Performance is quantified using the*inner ratio*vol\(⋃ℐ\)/vol\(BRSf\(𝒴\)\)\\vol\(\\bigcup\\mathcal\{I\}\)/\\vol\(\\BRS\_\{f\}\(\\mathcal\{Y\}\)\)and the*outer ratio*vol\(BRSf\(𝒴\)\)/vol\(⋃𝒪\)\\vol\(\\BRS\_\{f\}\(\\mathcal\{Y\}\)\)/\\vol\(\\bigcup\\mathcal\{O\}\), which evaluate the volumes of the estimated sets relative to the true backward reachable set \(BRS\), yielding a value of 1 for exact approximations\. Volumes are approximated using uniform samples from the input space\.
Table 1\.Performance comparison ofBernBRSversus the CROWN baseline with a time\-matched budget\. The data details inner ratios, outer ratios, solving times, and model parameters evaluated over three test images\.∙\\bulletExperiment 1: Correctness\.This experiment explicitly validates the mathematical correctness and geometric accuracy of theBernBRSframework\. We utilize random, untrained two\-input neural networks with two outputs and randomly assigned Bernstein activations\. The true BRS is computed over a fine grid to serve as an exact ground truth for comparison against the algorithm’s computed bounds\. Targets are defined as geometric boxes and triangles\.
Figure[4](https://arxiv.org/html/2611.22083#S6.F4)shows six networks of different widthww, depthRRand degreenn\. As shown in the figure,BernBRSdemonstrated strict soundness across 859 independent trials, maintaining inner ratios of at least 0\.97 and outer ratios of at least 0\.98 for select network configurations\. Crucially, no elements of the generated inner sets fell outside the true BRS, and no elements of the true BRS fell outside the outer sets\. While median inner ratios naturally decreased for deeper or wider architectures under strict computational budgets, scaling the allowed partitions to 32,000 consistently restored inner and outer ratios to 0\.90\.
∙\\bulletExperiment 2: Scalability Against State\-of\-the\-Art\.This experiment measures the computational scalability of the framework across increasingly complex neural network architectures\. The baseline method for comparison is the backward reachability technique in\([Rober et al\., 2023](https://arxiv.org/html/2611.22083#bib.bib26)\)which uses CROWN\-based linear relaxations of neural networks\([Zhang et al\., 2018](https://arxiv.org/html/2611.22083#bib.bib38)\)along with input space partitioning\. That method computes over\-approximations, and we add the corresponding under\-approximation\. We implement it for Bernstein layers and compare it withBernBRSon the image classifiers and the closed loop, on the same networks, samples and hardware\. We did not use PREMAP\([Zhang et al\., 2025](https://arxiv.org/html/2611.22083#bib.bib39)\)or INVPROP\([Kotha et al\., 2023](https://arxiv.org/html/2611.22083#bib.bib14)\)as baselines, because both are formulated for ReLU networks and their published versions do not cover Bernstein activations\.
The framework is tested on fully connected Bernstein image classifiers trained on MNIST\([LeCun et al\., 1998](https://arxiv.org/html/2611.22083#bib.bib16)\), GTSRB\([Stallkamp et al\., 2012](https://arxiv.org/html/2611.22083#bib.bib31)\)and CIFAR\-10\([Krizhevsky, 2009](https://arxiv.org/html/2611.22083#bib.bib15)\)datasets\. The input domains are defined as bounding boxes around test images, and targets are formulated to keep the label margin above its median value\.BernBRSis benchmarked directly against the CROWN\-based baseline restricted to an equivalent time allocation\. Appendix[E](https://arxiv.org/html/2611.22083#A5)gives the details of their training\. Each run uses anℓ∞\\ell\_\{\\infty\}box around one of three test images, with half\-width8/2558/255across widths and0\.020\.02across depths\. The target keeps the label margin above its median over the box, so the true share is about one half\. The baseline gets the time ofBernBRS: its element budget doubles from one, and we keep the last baseline run within the solve time ofBernBRSon that box\.
Table[1](https://arxiv.org/html/2611.22083#S7.T1)gives the results\. The baseline is never ahead\. It has an inner ratio of00on all108108runs and its outer set is the whole box on105105, although it makes a median of4,0954\{,\}095splits against about400400forBernBRS\. From width100100to500500, the inner ratio ofBernBRSfalls from0\.430\.43–0\.650\.65to0\.370\.37–0\.480\.48on Bernstein network 1 and from0\.160\.16–0\.700\.70to0\.020\.02–0\.140\.14on Bernstein network 2\. From depth22to44, it falls from0\.730\.73–0\.840\.84to0\.610\.61–0\.770\.77on Bernstein network 1 and from0\.430\.43–0\.840\.84to0\.380\.38–0\.800\.80on Bernstein network 2\. The solve takes at most176176s per run\. The test accuracy is at least96\.696\.6% on MNIST,88\.988\.9% on GTSRB and48\.248\.2% on CIFAR\-10\. All runs pass the soundness check\.
Table 2\.Five text sentences targeting a positive label, evaluated with their free words in bold\. The columns contrast the BRS words certified by theBernBRSstudent model against words eliciting a positive label from TinyBERT\.∙\\bulletCase Study 1: A Hybrid Dynamical Control System\.The first case study appliesBernBRSto a trained controller in closed loop\. A Bernstein network with one hidden layer of 128 units, trained by PPO\([Schulman et al\., 2017](https://arxiv.org/html/2611.22083#bib.bib28)\)with certified training, controls HalfCheetah in MuJoCo\([Todorov et al\., 2012](https://arxiv.org/html/2611.22083#bib.bib32)\), a simulated robot with 17 states and 6 actions\. We linearize the simulator step along a logged trajectory\. For each time step, we merge the one\-layer policy with the linearized dynamics, which gives two layers per step, so akk\-step network has2k2klayers\. We do this up tok=20k=20, which gives a network of depth4040\. Appendix[F](https://arxiv.org/html/2611.22083#A6)gives the details of the merge, the training and the settings\.
All backward reachable sets computed in this section are sets of initial states of the linearized closed\-loop model for which the merged Bernstein network reaches the specified pitch target\. They do not constitute formal safety or failure guarantees for the original MuJoCo plant or for any physical realization of HalfCheetah\. Contact changes and model mismatch might lead to discrepancies between the linearized model and MuJoCo at longer horizons; these discrepancies should be understood as unmodeled plant uncertainty that lies outside the scope of the current certification framework which focuses solely on the neural network controller\.
After training, we run the controller 50 times for 1,000 steps each, with a deterministic policy and deterministic dynamics, from different random initial states\. The robot falls in 8 of these runs, where the pitch passes 1 rad without recovery, and we analyze 5 of these falls\. For each fall, the target is a pitch of at least 1 rad at the stepEEtwo steps after the logged pitch first passes 1 rad\. Fork=1,…,20k=1,\\dots,20, we compute the BRS over a box around the logged statekksteps beforeEE, where one step is 0\.05 s\. The wide box has half\-widthS16S\_\{16\}on all 17 state coordinates, and the thin box keepsS16S\_\{16\}on the pitch, the pitch rate and the forward speed and usesS4S\_\{4\}elsewhere, whereSmS\_\{m\}ismmtimes a representative sensor error per coordinate \(Tables[6](https://arxiv.org/html/2611.22083#A6.T6)and[7](https://arxiv.org/html/2611.22083#A6.T7)\)\. This gives 200 runs atN=2,000N=2\{,\}000\.
Figure 5\.Certificate tightness plotted against the number of backward steps from the target across five failure scenarios\. Curves represent box shares: green for theBernBRSinner set, blue for states outside the outer set, and black for the true share\. Dashed lines indicate the CROWN baseline’s performance within an equivalent timeframe\.Figure[5](https://arxiv.org/html/2611.22083#S7.F5)shows the shares of the union of the five falls\. Green is the inner set, the share of the union that is certified to fall\. Blue is the share that lies outside the outer set, which is certified not to fall\. The lower dashed line is the inner share of the baseline, and the upper dashed line is its outer share\. The black line in the middle is the true share, and the closer the inner and outer shares lie to it, the tighter the BRS is\.
We then replay in MuJoCo the states certified to fall, among 4,000 uniform samples of each box, to check them\. Figure[6](https://arxiv.org/html/2611.22083#A6.F6)in the appendix shows a logged fall as an example of such a trajectory\.
∙\\bulletCase Study 2: TinyBERT Transformer\.The second case study appliesBernBRSto a transformer\. We take TinyBERT\([Jiao et al\., 2020](https://arxiv.org/html/2611.22083#bib.bib11)\)with a classifier, fine\-tuned on the sentiment dataset SST\-2\([Socher et al\., 2013](https://arxiv.org/html/2611.22083#bib.bib30)\)\. We distill its last block and classifier into a Bernstein student, which gives the same prediction as TinyBERT on99\.2%99\.2\\,\\%of the development sentences\. The student has three attention heads with a monotone Bernstein gate of degree99in place of the softmax, an MLP of300300Bernstein neurons and312312more before the classifier \(Appendix[G](https://arxiv.org/html/2611.22083#A7)\)\.
We take5050random development sentences and keep the4343that TinyBERT and the student classify correctly\. We free one word of each sentence and keep the other words fixed, so the student depends only on the312312numbers that represent this word at the input of the block\. We then useBernBRSon the student, through an exact rewrite \(Appendix[G\.2](https://arxiv.org/html/2611.22083#A7.SS2)\)\. The input set is a box around the free word, in which each number moves by at most one standard deviation of that number over the training tokens \(ϵσi\\epsilon\\sigma\_\{i\}withϵ=1\\epsilon=1\)\. We set the target to the true label of the sentence and take the inner set\. An input in the inner set is certified to keep that label\.
We then test the result on TinyBERT\. We take all the candidate words that fall in the4343boxes, which are6,3216\{,\}321words, counted once per box, and place each one in its sentence\.BernBRSproves that6,3206\{,\}320of these words keep the label on the student, and the remaining word falls in the undecided set\. We run TinyBERT on the changed sentences, and all6,3216\{,\}321words keep the same label\. This test covers these words only and is not a guarantee for TinyBERT: our backward\-reachability certificates apply exclusively to the distilled Bernstein student network obtained by our exact rewrite, under the idealized mathematical model\. TinyBERT itself remains unchecked; we only report empirical agreement between TinyBERT and the student on the probed substitutions\. Table[2](https://arxiv.org/html/2611.22083#S7.T2)shows five sentences with a positive label\. In all five, the words proven on the student also give the positive label on TinyBERT, including words with a negative meaning, such as “ruthless”\.
## Acknowledgment
This work was partially supported by the NSF award CNS \#2504809 and the UCI ProperAI Institute, an Engineering\+Society Institute funded as part of a generous gift from Susan and Henry Samueli\.
## References
- Bansal et al\.\(2017\)Somil Bansal, Mo Chen, Sylvia Herbert, and Claire J\. Tomlin\. 2017\.Hamilton–Jacobi Reachability: A Brief Overview and Recent Advances\. In*2017 IEEE 56th Annual Conference on Decision and Control \(CDC\)*\. 2242–2253\.[doi:10\.1109/CDC\.2017\.8263977](https://doi.org/10.1109/CDC.2017.8263977)
- Devlin et al\.\(2019\)Jacob Devlin, Ming\-Wei Chang, Kenton Lee, and Kristina Toutanova\. 2019\.BERT: Pre\-training of Deep Bidirectional Transformers for Language Understanding\. In*Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies \(NAACL\-HLT\)*\. 4171–4186\.[doi:10\.18653/v1/N19\-1423](https://doi.org/10.18653/v1/N19-1423)
- Dutta et al\.\(2019\)Souradeep Dutta, Xin Chen, and Sriram Sankaranarayanan\. 2019\.Reachability Analysis for Neural Feedback Systems Using Regressive Polynomial Rule Inference\. In*Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control \(HSCC\)*\. ACM, 157–168\.[doi:10\.1145/3302504\.3311807](https://doi.org/10.1145/3302504.3311807)
- Everett et al\.\(2021\)Michael Everett, Golnaz Habibi, Chuangchuang Sun, and Jonathan P\. How\. 2021\.Reachability Analysis of Neural Feedback Loops\.*IEEE Access*9 \(2021\), 163938–163953\.[doi:10\.1109/ACCESS\.2021\.3133370](https://doi.org/10.1109/ACCESS.2021.3133370)
- Farouki \(2012\)Rida T\. Farouki\. 2012\.The Bernstein Polynomial Basis: A Centennial Retrospective\.*Computer Aided Geometric Design*29, 6 \(2012\), 379–419\.[doi:10\.1016/j\.cagd\.2012\.03\.001](https://doi.org/10.1016/j.cagd.2012.03.001)
- Gowal et al\.\(2019\)Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Arthur Mann, and Pushmeet Kohli\. 2019\.Scalable Verified Training for Provably Robust Image Classification\. In*2019 IEEE/CVF International Conference on Computer Vision \(ICCV\)*\. 4841–4850\.[doi:10\.1109/ICCV\.2019\.00494](https://doi.org/10.1109/ICCV.2019.00494)
- Hinton et al\.\(2015\)Geoffrey Hinton, Oriol Vinyals, and Jeff Dean\. 2015\.Distilling the Knowledge in a Neural Network\.*arXiv preprint arXiv:1503\.02531*\(2015\)\.Presented at the NIPS 2014 Deep Learning Workshop\.
- Huang et al\.\(2019\)Chao Huang, Jiameng Fan, Wenchao Li, Xin Chen, and Qi Zhu\. 2019\.ReachNN: Reachability Analysis of Neural\-Network Controlled Systems\.*ACM Transactions on Embedded Computing Systems*18, 5s \(2019\), 1–22\.[doi:10\.1145/3358228](https://doi.org/10.1145/3358228)
- Ivanov et al\.\(2019\)Radoslav Ivanov, James Weimer, Rajeev Alur, George J\. Pappas, and Insup Lee\. 2019\.Verisig: Verifying Safety Properties of Hybrid Systems with Neural Network Controllers\. In*Proceedings of the 22nd ACM International Conference on Hybrid Systems: Computation and Control \(HSCC\)*\. ACM, 169–178\.[doi:10\.1145/3302504\.3311806](https://doi.org/10.1145/3302504.3311806)
- Jiao et al\.\(2020\)Xiaoqi Jiao, Yichun Yin, Lifeng Shang, Xin Jiang, Xiao Chen, Linlin Li, Fang Wang, and Qun Liu\. 2020\.TinyBERT: Distilling BERT for Natural Language Understanding\. In*Findings of the Association for Computational Linguistics: EMNLP 2020*\. 4163–4174\.[doi:10\.18653/v1/2020\.findings\-emnlp\.372](https://doi.org/10.18653/v1/2020.findings-emnlp.372)
- Katz et al\.\(2017\)Guy Katz, Clark Barrett, David L\. Dill, Kyle Julian, and Mykel J\. Kochenderfer\. 2017\.Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks\. In*Computer Aided Verification \(CAV\)**\(LNCS, Vol\. 10426\)*\. Springer, 97–117\.[doi:10\.1007/978\-3\-319\-63387\-9\_5](https://doi.org/10.1007/978-3-319-63387-9_5)
- Khedr and Shoukry \(2024\)Haitham Khedr and Yasser Shoukry\. 2024\.DeepBern\-Nets: Taming the Complexity of Certifying Neural Networks Using Bernstein Polynomial Activations and Precise Bound Propagation\. In*Proceedings of the AAAI Conference on Artificial Intelligence*, Vol\. 38\. 21232–21240\.[doi:10\.1609/aaai\.v38i19\.30117](https://doi.org/10.1609/aaai.v38i19.30117)
- Kotha et al\.\(2023\)Suhas Kotha, Christopher Brix, J\. Zico Kolter, Krishnamurthy Dvijotham, and Huan Zhang\. 2023\.Provably Bounding Neural Network Preimages\. In*Advances in Neural Information Processing Systems 36 \(NeurIPS 2023\)*\. 80270–80290\.[doi:10\.52202/075280\-3518](https://doi.org/10.52202/075280-3518)
- Krizhevsky \(2009\)Alex Krizhevsky\. 2009\.*Learning Multiple Layers of Features from Tiny Images*\.Technical Report\. Department of Computer Science, University of Toronto\.
- LeCun et al\.\(1998\)Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner\. 1998\.Gradient\-Based Learning Applied to Document Recognition\.*Proc\. IEEE*86, 11 \(1998\), 2278–2324\.[doi:10\.1109/5\.726791](https://doi.org/10.1109/5.726791)
- Liu et al\.\(2021\)Changliu Liu, Tomer Arnon, Christopher Lazarus, Christopher Strong, Clark Barrett, and Mykel J\. Kochenderfer\. 2021\.Algorithms for Verifying Deep Neural Networks\.*Foundations and Trends in Optimization*4, 3–4 \(2021\), 244–404\.[doi:10\.1561/2400000035](https://doi.org/10.1561/2400000035)
- Matoba and Fleuret \(2020\)Kyle Matoba and François Fleuret\. 2020\.Exact Preimages of Neural Network Aircraft Collision Avoidance Systems\. In*NeurIPS 2020 Workshop on Machine Learning for Engineering Modeling, Simulation, and Design \(ML4Eng\)*\.
- Mitchell \(2007\)Ian M\. Mitchell\. 2007\.Comparing Forward and Backward Reachability as Tools for Safety Analysis\. In*Hybrid Systems: Computation and Control \(HSCC\)**\(LNCS, Vol\. 4416\)*\. Springer, 428–443\.[doi:10\.1007/978\-3\-540\-71493\-4\_34](https://doi.org/10.1007/978-3-540-71493-4_34)
- Mitchell et al\.\(2005\)Ian M\. Mitchell, Alexandre M\. Bayen, and Claire J\. Tomlin\. 2005\.A Time\-Dependent Hamilton–Jacobi Formulation of Reachable Sets for Continuous Dynamic Games\.*IEEE Trans\. Automat\. Control*50, 7 \(2005\), 947–957\.[doi:10\.1109/TAC\.2005\.851439](https://doi.org/10.1109/TAC.2005.851439)
- Prautzsch et al\.\(2002\)Hartmut Prautzsch, Wolfgang Boehm, and Marco Paluszny\. 2002\.*Bézier and B\-Spline Techniques*\.Springer\.[doi:10\.1007/978\-3\-662\-04919\-8](https://doi.org/10.1007/978-3-662-04919-8)
- Raffin \(2020\)Antonin Raffin\. 2020\.RL Baselines3 Zoo\.[https://github\.com/DLR\-RM/rl\-baselines3\-zoo](https://github.com/DLR-RM/rl-baselines3-zoo)\.
- Raffin et al\.\(2021\)Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann\. 2021\.Stable\-Baselines3: Reliable Reinforcement Learning Implementations\.*Journal of Machine Learning Research*22, 268 \(2021\), 1–8\.
- Ramshaw \(1989\)Lyle Ramshaw\. 1989\.Blossoms Are Polar Forms\.*Computer Aided Geometric Design*6, 4 \(1989\), 323–358\.[doi:10\.1016/0167\-8396\(89\)90032\-0](https://doi.org/10.1016/0167-8396(89)90032-0)
- Rober et al\.\(2022\)Nicholas Rober, Michael Everett, and Jonathan P\. How\. 2022\.Backward Reachability Analysis for Neural Feedback Loops\. In*2022 IEEE 61st Conference on Decision and Control \(CDC\)*\. 2897–2904\.[doi:10\.1109/CDC51059\.2022\.9992847](https://doi.org/10.1109/CDC51059.2022.9992847)
- Rober et al\.\(2023\)Nicholas Rober, Sydney M\. Katz, Chelsea Sidrane, Esen Yel, Michael Everett, Mykel J\. Kochenderfer, and Jonathan P\. How\. 2023\.Backward Reachability Analysis of Neural Feedback Loops: Techniques for Linear and Nonlinear Systems\.*IEEE Open Journal of Control Systems*2 \(2023\), 108–124\.[doi:10\.1109/OJCSYS\.2023\.3265901](https://doi.org/10.1109/OJCSYS.2023.3265901)
- Schilling et al\.\(2022\)Christian Schilling, Marcelo Forets, and Sebastián Guadalupe\. 2022\.Verification of Neural\-Network Control Systems by Integrating Taylor Models and Zonotopes\. In*Proceedings of the AAAI Conference on Artificial Intelligence*, Vol\. 36\. 8169–8177\.[doi:10\.1609/aaai\.v36i7\.20790](https://doi.org/10.1609/aaai.v36i7.20790)
- Schulman et al\.\(2017\)John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov\. 2017\.Proximal Policy Optimization Algorithms\.*arXiv preprint arXiv:1707\.06347*\(2017\)\.
- Shi et al\.\(2025\)Zhouxing Shi, Qirui Jin, Zico Kolter, Suman Jana, Cho\-Jui Hsieh, and Huan Zhang\. 2025\.Neural Network Verification with Branch\-and\-Bound for General Nonlinearities\. In*Tools and Algorithms for the Construction and Analysis of Systems \(TACAS\)*\.
- Socher et al\.\(2013\)Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D\. Manning, Andrew Y\. Ng, and Christopher Potts\. 2013\.Recursive Deep Models for Semantic Compositionality over a Sentiment Treebank\. In*Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing \(EMNLP\)*\. 1631–1642\.[doi:10\.18653/v1/D13\-1170](https://doi.org/10.18653/v1/D13-1170)
- Stallkamp et al\.\(2012\)Johannes Stallkamp, Marc Schlipsing, Jan Salmen, and Christian Igel\. 2012\.Man vs\. Computer: Benchmarking Machine Learning Algorithms for Traffic Sign Recognition\.*Neural Networks*32 \(2012\), 323–332\.[doi:10\.1016/j\.neunet\.2012\.02\.016](https://doi.org/10.1016/j.neunet.2012.02.016)
- Todorov et al\.\(2012\)Emanuel Todorov, Tom Erez, and Yuval Tassa\. 2012\.MuJoCo: A Physics Engine for Model\-Based Control\. In*2012 IEEE/RSJ International Conference on Intelligent Robots and Systems \(IROS\)*\. 5026–5033\.[doi:10\.1109/IROS\.2012\.6386109](https://doi.org/10.1109/IROS.2012.6386109)
- Towers et al\.\(2025\)Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U\. Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, Rodrigo Perez\-Vicente, Andrea Pierré, Sander Schulhoff, Jun Jet Tai, Hannah Tan, and Omar G\. Younis\. 2025\.Gymnasium: A Standard Interface for Reinforcement Learning Environments\. In*Advances in Neural Information Processing Systems 38 \(NeurIPS 2025\), Datasets and Benchmarks Track*\. 163114–163129\.[doi:10\.52202/085713\-4916](https://doi.org/10.52202/085713-4916)
- Tran et al\.\(2020\)Hoang\-Dung Tran, Xiaodong Yang, Diego Manzanas Lopez, Patrick Musau, Luan Viet Nguyen, Weiming Xiang, Stanley Bak, and Taylor T\. Johnson\. 2020\.NNV: The Neural Network Verification Tool for Deep Neural Networks and Learning\-Enabled Cyber\-Physical Systems\. In*Computer Aided Verification \(CAV\)**\(LNCS, Vol\. 12224\)*\. Springer, 3–17\.[doi:10\.1007/978\-3\-030\-53288\-8\_1](https://doi.org/10.1007/978-3-030-53288-8_1)
- Vincent and Schwager \(2021\)Joseph A\. Vincent and Mac Schwager\. 2021\.Reachable Polyhedral Marching \(RPM\): A Safety Verification Algorithm for Robotic Systems with Deep Neural Network Components\. In*IEEE International Conference on Robotics and Automation \(ICRA\)*\. 9029–9035\.[doi:10\.1109/ICRA48506\.2021\.9561956](https://doi.org/10.1109/ICRA48506.2021.9561956)
- Wang et al\.\(2019\)Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R\. Bowman\. 2019\.GLUE: A Multi\-Task Benchmark and Analysis Platform for Natural Language Understanding\. In*International Conference on Learning Representations \(ICLR\)*\.
- Wang et al\.\(2021\)Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho\-Jui Hsieh, and J\. Zico Kolter\. 2021\.Beta\-CROWN: Efficient Bound Propagation with Per\-Neuron Split Constraints for Neural Network Robustness Verification\. In*Advances in Neural Information Processing Systems 34 \(NeurIPS 2021\)*\. 29909–29921\.
- Zhang et al\.\(2018\)Huan Zhang, Tsui\-Wei Weng, Pin\-Yu Chen, Cho\-Jui Hsieh, and Luca Daniel\. 2018\.Efficient Neural Network Robustness Certification with General Activation Functions\. In*Advances in Neural Information Processing Systems 31 \(NeurIPS 2018\)*\.
- Zhang et al\.\(2025\)Xiyue Zhang, Benjie Wang, Marta Kwiatkowska, and Huan Zhang\. 2025\.PREMAP: A Unifying PREiMage APproximation Framework for Neural Networks\.*Journal of Machine Learning Research*26, 133 \(2025\), 1–44\.
## Appendices
## Appendix AForward Bounding
This appendix proves the statements of Section[4](https://arxiv.org/html/2611.22083#S4)\. It also states Remark[A\.2](https://arxiv.org/html/2611.22083#A1.Thmtheorem2)and Proposition[A\.3](https://arxiv.org/html/2611.22083#A1.Thmtheorem3), which that section cites\.
### A\.1\.Interval Bounds over a Pattern
###### Lemma A\.1 \(Interval bounds over a pattern\)\.
Let the bounds be given by \([8](https://arxiv.org/html/2611.22083#S4.E8)\) and \([9](https://arxiv.org/html/2611.22083#S4.E9)\), with\[σ¯\(0\),σ¯\(0\)\]=X^\[\\underline\{\\sigma\}^\{\(0\)\},\\overline\{\\sigma\}^\{\(0\)\}\]=\\hat\{X\}\. Thenz\(r\)\(x\)∈\[z¯\(r\),z¯\(r\)\]z^\{\(r\)\}\(x\)\\in\[\\underline\{z\}^\{\(r\)\},\\overline\{z\}^\{\(r\)\}\]andσ\(r\)\(z\(r\)\(x\)\)∈\[σ¯\(r\),σ¯\(r\)\]\\sigma^\{\(r\)\}\(z^\{\(r\)\}\(x\)\)\\in\[\\underline\{\\sigma\}^\{\(r\)\},\\overline\{\\sigma\}^\{\(r\)\}\]for everyx∈ℛ\(P\)x\\in\\mathcal\{R\}\(P\)andr∈\[R\]r\\in\[R\]\. Ifz¯j\(r\)\>z¯j\(r\)\\underline\{z\}^\{\(r\)\}\_\{j\}\>\\overline\{z\}^\{\(r\)\}\_\{j\}for some neuron, thenℛ\(P\)=∅\\mathcal\{R\}\(P\)=\\emptyset\.
###### Proof of Lemma[A\.1](https://arxiv.org/html/2611.22083#A1.Thmtheorem1)\.
By induction onrr\. SplittingWrW\_\{r\}into its positive and negative parts shows that the first arguments in \([8](https://arxiv.org/html/2611.22083#S4.E8)\) enclosez\(r\)\(x\)z^\{\(r\)\}\(x\)forx∈X^x\\in\\hat\{X\}whose post\-activations lie in the previous bounds\. Forx∈ℛ\(P\)x\\in\\mathcal\{R\}\(P\), alsoz\(r\)\(x\)∈Z^\(r\)z^\{\(r\)\}\(x\)\\in\\hat\{Z\}^\{\(r\)\}by Definition[2\.2](https://arxiv.org/html/2611.22083#S2.Thmtheorem2), hence the maximum and minimum\. The post\-activation bounds follow from Lemma[B\.1](https://arxiv.org/html/2611.22083#A2.Thmtheorem1), applied to the interval\[z¯j\(r\),z¯j\(r\)\]\[\\underline\{z\}^\{\(r\)\}\_\{j\},\\overline\{z\}^\{\(r\)\}\_\{j\}\]that containszj\(r\)\(x\)z^\{\(r\)\}\_\{j\}\(x\)\. If the interval of a neuron is empty, noxxsatisfies the constraints\. ∎
### A\.2\.Bernstein Linear Relaxation
###### Proof of Lemma[4\.1](https://arxiv.org/html/2611.22083#S4.Thmtheorem1)\.
Letp\(z\)=σj\(r\)\(z\)−szp\(z\)=\\sigma^\{\(r\)\}\_\{j\}\(z\)\-sz, a polynomial of degree at mostnn\. By \(P4\), the Bernstein coefficients ofz↦szz\\mapsto szon\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]aresξis\\,\\xi\_\{i\}\. By linearity of the Bernstein form, the Bernstein coefficients ofppon this interval areeie\_\{i\}\. By \(P1\),miniei≤p\(z\)≤maxiei\\min\_\{i\}e\_\{i\}\\leq p\(z\)\\leq\\max\_\{i\}e\_\{i\}forz∈\[z¯,z¯\]z\\in\[\\underline\{z\},\\overline\{z\}\]\. ∎
Forz¯=z¯\\overline\{z\}=\\underline\{z\}any slope is valid, and the implementation uses the derivative of the activation atz¯\\underline\{z\}\. With the secant slope,e0=ene\_\{0\}=e\_\{n\}\. Minimizingβ\\betaover the slopessis an option:β¯\\overline\{\\beta\}is a maximum andβ¯\\underline\{\\beta\}a minimum of functions that are affine inss, soβ\\betais a convex piecewise\-linear function ofss\. The main runs use the secant slope\.
### A\.3\.Offsets fromJJSub\-intervals
###### Proof of Remark[A\.2](https://arxiv.org/html/2611.22083#A1.Thmtheorem2)\.
\(i\) Letz∈\[z¯,z¯\]z\\in\[\\underline\{z\},\\overline\{z\}\]\. Thenzzlies in some sub\-interval\[ak,bk\]\[a\_\{k\},b\_\{k\}\]\. By \(P4\) and linearity,e\(k\)e^\{\(k\)\}are the Bernstein coefficients ofp\(z\)=σ\(z\)−szp\(z\)=\\sigma\(z\)\-szon\[ak,bk\]\[a\_\{k\},b\_\{k\}\], and \(P1\) givesp\(z\)∈\[miniei\(k\),maxiei\(k\)\]p\(z\)\\in\[\\min\_\{i\}e^\{\(k\)\}\_\{i\},\\max\_\{i\}e^\{\(k\)\}\_\{i\}\]\. \(ii\) The polynomialpphas Bernstein coefficientseeon\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]\. By \(P2\), its Bernstein coefficientse\(k\)e^\{\(k\)\}on the sub\-interval\[ak,bk\]\[a\_\{k\},b\_\{k\}\]are convex combinations ofe0,…,ene\_\{0\},\\dots,e\_\{n\}\. Henceminiei≤ei\(k\)≤maxiei\\min\_\{i\}e\_\{i\}\\leq e^\{\(k\)\}\_\{i\}\\leq\\max\_\{i\}e\_\{i\}for allkkandii\. ∎
### A\.4\.Quadratic Relaxation Width
###### Proposition A\.3 \(Quadratic relaxation width\)\.
Letn≥2n\\geq 2, let\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]have widthw=z¯−z¯w=\\overline\{z\}\-\\underline\{z\}, and letΓ2≥0\\Gamma\_\{2\}\\geq 0bound the absolute values of the Bernstein coefficients of\(σj\(r\)\)′′\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\\prime\}on it\. With the secant slope,
\(16\)β¯−β¯≤n4\(n−1\)Γ2w2\.\\overline\{\\beta\}\-\\underline\{\\beta\}\\;\\leq\\;\\frac\{n\}\{4\(n\-1\)\}\\,\\Gamma\_\{2\}\\,w^\{2\}\.By item \(ii\) of Remark[A\.2](https://arxiv.org/html/2611.22083#A1.Thmtheorem2), the bound also holds for the sub\-interval offsets\.
###### Proof of Proposition[A\.3](https://arxiv.org/html/2611.22083#A1.Thmtheorem3)\.
The offsets areminiei\\min\_\{i\}e\_\{i\}andmaxiei\\max\_\{i\}e\_\{i\}by Lemma[4\.1](https://arxiv.org/html/2611.22083#S4.Thmtheorem1)\. Letp\(s\)=σj\(r\)\(z¯\+ws\)p\(s\)=\\sigma^\{\(r\)\}\_\{j\}\(\\underline\{z\}\+ws\)\. Applying \(P3\) twice and the chain rule gives
p′′\(s\)=n\(n−1\)∑iΔ2ci′Bn−2,i\[0,1\]\(s\)=w2\(σj\(r\)\)′′\(z¯\+ws\),p^\{\\prime\\prime\}\(s\)=n\(n\-1\)\\sum\_\{i\}\\Delta^\{2\}c^\{\\prime\}\_\{i\}\\,B^\{\[0,1\]\}\_\{n\-2,i\}\(s\)=w^\{2\}\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\\prime\}\(\\underline\{z\}\+ws\),whereΔ2ci′=ci\+2′−2ci\+1′\+ci′\\Delta^\{2\}c^\{\\prime\}\_\{i\}=c^\{\\prime\}\_\{i\+2\}\-2c^\{\\prime\}\_\{i\+1\}\+c^\{\\prime\}\_\{i\}\. By uniqueness of the Bernstein form,Δ2ci′=w2ζi/\(n\(n−1\)\)\\Delta^\{2\}c^\{\\prime\}\_\{i\}=w^\{2\}\\zeta\_\{i\}/\(n\(n\-1\)\), whereζ\\zetaare the Bernstein coefficients of\(σj\(r\)\)′′\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\\prime\}on the interval\. Hence\|Δ2ci′\|≤D:=w2Γ2/\(n\(n−1\)\)\|\\Delta^\{2\}c^\{\\prime\}\_\{i\}\|\\leq D:=w^\{2\}\\Gamma\_\{2\}/\(n\(n\-1\)\)\. The linear termsξis\\,\\xi\_\{i\}does not change second differences, so\|Δ2ei\|≤D\|\\Delta^\{2\}e\_\{i\}\|\\leq D, and the secant slope givese0=ene\_\{0\}=e\_\{n\}\. Setui=ei−e0u\_\{i\}=e\_\{i\}\-e\_\{0\}andvi=Di\(n−i\)/2v\_\{i\}=D\\,i\(n\-i\)/2, so thatu0=un=v0=vn=0u\_\{0\}=u\_\{n\}=v\_\{0\}=v\_\{n\}=0andΔ2vi=−D\\Delta^\{2\}v\_\{i\}=\-D\. The sequencesu\+vu\+vandv−uv\-uhave second differencesΔ2ui−D≤0\\Delta^\{2\}u\_\{i\}\-D\\leq 0and−D−Δ2ui≤0\-D\-\\Delta^\{2\}u\_\{i\}\\leq 0\. They are concave and vanish at both ends, so they are non\-negative\. Hence\|ui\|≤vi≤n2D/8\|u\_\{i\}\|\\leq v\_\{i\}\\leq n^\{2\}D/8\. Both the smallest and the largesteie\_\{i\}lie withinn2D/8n^\{2\}D/8ofe0e\_\{0\}, soβ¯−β¯≤n2D/4=nΓ2w2/\(4\(n−1\)\)\\overline\{\\beta\}\-\\underline\{\\beta\}\\leq n^\{2\}D/4=n\\Gamma\_\{2\}w^\{2\}/\(4\(n\-1\)\)\. ∎
### A\.5\.Linear Bounds and Gap Identity
###### Proof of Theorem[4\.2](https://arxiv.org/html/2611.22083#S4.Thmtheorem2)\.
Forx∈ℛ\(P\)x\\in\\mathcal\{R\}\(P\)we haveHf\(x\)=Λ\(R\)σ\(R\)\(z\(R\)\(x\)\)\+ooutHf\(x\)=\\Lambda^\{\(R\)\}\\sigma^\{\(R\)\}\(z^\{\(R\)\}\(x\)\)\+o\_\{\\mathrm\{out\}\}\. Suppose thatHf\(x\)∈\[Λ\(r\)σ\(r\)\(z\(r\)\(x\)\)\+olo\(r\),Λ\(r\)σ\(r\)\(z\(r\)\(x\)\)\+oup\(r\)\]Hf\(x\)\\in\[\\Lambda^\{\(r\)\}\\sigma^\{\(r\)\}\(z^\{\(r\)\}\(x\)\)\+o\_\{\\mathrm\{lo\}\}^\{\(r\)\},\\allowbreak\\,\\Lambda^\{\(r\)\}\\sigma^\{\(r\)\}\(z^\{\(r\)\}\(x\)\)\+o\_\{\\mathrm\{up\}\}^\{\(r\)\}\]for constantsolo\(r\),oup\(r\)o^\{\(r\)\}\_\{\\mathrm\{lo\}\},o^\{\(r\)\}\_\{\\mathrm\{up\}\}\. By assumption,zj\(r\)\(x\)z^\{\(r\)\}\_\{j\}\(x\)lies in the interval on which neuron\(r,j\)\(r,j\)was relaxed, so \([10](https://arxiv.org/html/2611.22083#S4.E10)\) givesσj\(r\)\(zj\(r\)\(x\)\)∈\[sj\(r\)zj\(r\)\(x\)\+β¯j\(r\),sj\(r\)zj\(r\)\(x\)\+β¯\]j\(r\)\\sigma^\{\(r\)\}\_\{j\}\(z^\{\(r\)\}\_\{j\}\(x\)\)\\in\[s^\{\(r\)\}\_\{j\}z^\{\(r\)\}\_\{j\}\(x\)\+\\underline\{\\beta\}^\{\(r\)\}\_\{j\},s^\{\(r\)\}\_\{j\}z^\{\(r\)\}\_\{j\}\(x\)\+\\overline\{\\beta\}\{\}^\{\(r\)\}\_\{j\}\]\. Multiplying by the entries ofΛ\(r\)\\Lambda^\{\(r\)\}, the lower bound usesβ¯\\underline\{\\beta\}for positive entries andβ¯\\overline\{\\beta\}for negative ones, and the upper bound the opposite, while both share the linear partΓ\(r\)z\(r\)\(x\)\\Gamma^\{\(r\)\}z^\{\(r\)\}\(x\)\. Substitutingz\(r\)\(x\)=Wrσ\(r−1\)\(z\(r−1\)\(x\)\)\+brz^\{\(r\)\}\(x\)=W\_\{r\}\\sigma^\{\(r\-1\)\}\(z^\{\(r\-1\)\}\(x\)\)\+b\_\{r\}yields the same statement at layerr−1r\-1with coefficientΛ\(r−1\)\\Lambda^\{\(r\-1\)\}\. Atr=0r=0,σ\(0\)\(z\(0\)\(x\)\)=x\\sigma^\{\(0\)\}\(z^\{\(0\)\}\(x\)\)=x\. Since both bounds share everyΛ\(r\)\\Lambda^\{\(r\)\}, they differ only in their constants, andcup−clo=∑r\(Λ\(r\)\+−Λ\(r\)−\)β\(r\)=∑r\|Λ\(r\)\|β\(r\)c\_\{\\mathrm\{up\}\}\-c\_\{\\mathrm\{lo\}\}=\\sum\_\{r\}\(\\Lambda^\{\(r\)\+\}\-\\Lambda^\{\(r\)\-\}\)\\beta^\{\(r\)\}=\\sum\_\{r\}\|\\Lambda^\{\(r\)\}\|\\beta^\{\(r\)\}\. ∎
## Appendix BBackward Contraction
This appendix proves the statements of Section[5](https://arxiv.org/html/2611.22083#S5)\. It also states Lemma[B\.1](https://arxiv.org/html/2611.22083#A2.Thmtheorem1), which that section cites\.
### B\.1\.Backward Interval Propagation over One Layer
###### Proof of Lemma[5\.1](https://arxiv.org/html/2611.22083#S5.Thmtheorem1)\.
Fix a rowjjandkkwithWjk≠0W\_\{jk\}\\neq 0\. Forσk′∈\[σ¯k′,σ¯k′\]\\sigma\_\{k^\{\\prime\}\}\\in\[\\underline\{\\sigma\}\_\{k^\{\\prime\}\},\\overline\{\\sigma\}\_\{k^\{\\prime\}\}\], the termWjk′σk′W\_\{jk^\{\\prime\}\}\\sigma\_\{k^\{\\prime\}\}is at mostWjk′\+σ¯k′\+Wjk′−σ¯k′W^\{\+\}\_\{jk^\{\\prime\}\}\\overline\{\\sigma\}\_\{k^\{\\prime\}\}\+W^\{\-\}\_\{jk^\{\\prime\}\}\\underline\{\\sigma\}\_\{k^\{\\prime\}\}and at leastWjk′\+σ¯k′\+Wjk′−σ¯k′W^\{\+\}\_\{jk^\{\\prime\}\}\\underline\{\\sigma\}\_\{k^\{\\prime\}\}\+W^\{\-\}\_\{jk^\{\\prime\}\}\\overline\{\\sigma\}\_\{k^\{\\prime\}\}, as in Lemma[A\.1](https://arxiv.org/html/2611.22083#A1.Thmtheorem1)\. Summing overk′≠kk^\{\\prime\}\\neq kbounds the other terms of rowjjby the two sums of the statement\. Subtracting these sums andbjb\_\{j\}fromz¯j′≤∑k′Wjk′σk′\+bj≤z¯j′\\underline\{z\}^\{\\prime\}\_\{j\}\\leq\\sum\_\{k^\{\\prime\}\}W\_\{jk^\{\\prime\}\}\\sigma\_\{k^\{\\prime\}\}\+b\_\{j\}\\leq\\overline\{z\}^\{\\prime\}\_\{j\}gives the interval forWjkσkW\_\{jk\}\\sigma\_\{k\}\. Dividing byWjkW\_\{jk\}keeps the order of the ends whenWjk\>0W\_\{jk\}\>0and reverses it whenWjk<0W\_\{jk\}<0\. Every row holds forσ\\sigma, soσk\\sigma\_\{k\}lies in all these intervals and in\[σ¯k,σ¯k\]\[\\underline\{\\sigma\}\_\{k\},\\overline\{\\sigma\}\_\{k\}\]\. If their intersection is empty, no suchσ\\sigmaexists\. ∎
### B\.2\.Monotonicity Certificate
###### Lemma B\.1 \(Monotonicity certificate\)\.
Let\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]be a bounded interval, and letc′c^\{\\prime\}be the Bernstein coefficients ofσj\(r\)\\sigma^\{\(r\)\}\_\{j\}on it\. Then:
1. \(1\)σj\(r\)\(\[z¯,z¯\]\)⊆\[minici′,maxici′\]\\sigma^\{\(r\)\}\_\{j\}\(\[\\underline\{z\},\\overline\{z\}\]\)\\subseteq\[\\min\_\{i\}c^\{\\prime\}\_\{i\},\\max\_\{i\}c^\{\\prime\}\_\{i\}\], andc0′=σj\(r\)\(z¯\)c^\{\\prime\}\_\{0\}=\\sigma^\{\(r\)\}\_\{j\}\(\\underline\{z\}\),cn′=σj\(r\)\(z¯\)c^\{\\prime\}\_\{n\}=\\sigma^\{\(r\)\}\_\{j\}\(\\overline\{z\}\)\.
2. \(2\)Ifci\+1′≥ci′c^\{\\prime\}\_\{i\+1\}\\geq c^\{\\prime\}\_\{i\}for allii, thenσj\(r\)\\sigma^\{\(r\)\}\_\{j\}is non\-decreasing on\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]and its image is\[σj\(r\)\(z¯\),σj\(r\)\(z¯\)\]\[\\sigma^\{\(r\)\}\_\{j\}\(\\underline\{z\}\),\\sigma^\{\(r\)\}\_\{j\}\(\\overline\{z\}\)\]\. Symmetrically, ifci\+1′≤ci′c^\{\\prime\}\_\{i\+1\}\\leq c^\{\\prime\}\_\{i\}for allii, it is non\-increasing and the image is\[σj\(r\)\(z¯\),σj\(r\)\(z¯\)\]\[\\sigma^\{\(r\)\}\_\{j\}\(\\overline\{z\}\),\\sigma^\{\(r\)\}\_\{j\}\(\\underline\{z\}\)\]\.
If item 2 applies, the neuron is*certified monotone*on\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\], more precisely certified non\-decreasing or certified non\-increasing\. The test is sufficient only\.
###### Proof of Lemma[B\.1](https://arxiv.org/html/2611.22083#A2.Thmtheorem1)\.
Letp\(s\)=σj\(r\)\(z¯\+\(z¯−z¯\)s\)p\(s\)=\\sigma^\{\(r\)\}\_\{j\}\(\\underline\{z\}\+\(\\overline\{z\}\-\\underline\{z\}\)s\), whose Bernstein coefficients on\[0,1\]\[0,1\]arec′c^\{\\prime\}by \(P2\)\. The enclosure and the end valuesc0′=σj\(r\)\(z¯\)c^\{\\prime\}\_\{0\}=\\sigma^\{\(r\)\}\_\{j\}\(\\underline\{z\}\),cn′=σj\(r\)\(z¯\)c^\{\\prime\}\_\{n\}=\\sigma^\{\(r\)\}\_\{j\}\(\\overline\{z\}\)are \(P1\), which proves item 1\. By \(P3\),
p′\(s\)=n∑i\(ci\+1′−ci′\)Bn−1,i\[0,1\]\(s\),p^\{\\prime\}\(s\)=n\\sum\_\{i\}\(c^\{\\prime\}\_\{i\+1\}\-c^\{\\prime\}\_\{i\}\)\\,B^\{\[0,1\]\}\_\{n\-1,i\}\(s\),whose Bernstein coefficientsn\(ci\+1′−ci′\)n\(c^\{\\prime\}\_\{i\+1\}\-c^\{\\prime\}\_\{i\}\)are non\-negative ifci\+1′≥ci′c^\{\\prime\}\_\{i\+1\}\\geq c^\{\\prime\}\_\{i\}for allii\. By \(P1\) applied top′p^\{\\prime\},p′≥0p^\{\\prime\}\\geq 0on\[0,1\]\[0,1\], soσj\(r\)\\sigma^\{\(r\)\}\_\{j\}is non\-decreasing on\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]\. A continuous non\-decreasing function maps an interval onto the interval between its endpoint values\. The non\-increasing case follows by applying this to−p\-p\. This proves item 2\. ∎
### B\.3\.Inverse of a Certified Monotone Activation
###### Proof of Lemma[5\.2](https://arxiv.org/html/2611.22083#S5.Thmtheorem2)\.
The functionσ\\sigmais continuous and non\-decreasing on\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]by Lemma[B\.1](https://arxiv.org/html/2611.22083#A2.Thmtheorem1)\. It need not be strictly increasing\. LetS=\{z∈\[z¯,z¯\]:σ\(z\)∈\[σ¯′,σ¯′\]\}S=\\\{z\\in\[\\underline\{z\},\\overline\{z\}\]:\\sigma\(z\)\\in\[\\underline\{\\sigma\}^\{\\prime\},\\overline\{\\sigma\}^\{\\prime\}\]\\\}\.
*Item 1\.*Ifσ\(z¯\)<σ¯′\\sigma\(\\overline\{z\}\)<\\underline\{\\sigma\}^\{\\prime\}, thenσ\(z\)≤σ\(z¯\)<σ¯′\\sigma\(z\)\\leq\\sigma\(\\overline\{z\}\)<\\underline\{\\sigma\}^\{\\prime\}for everyzz, and ifσ\(z¯\)\>σ¯′\\sigma\(\\underline\{z\}\)\>\\overline\{\\sigma\}^\{\\prime\}, thenσ\(z\)≥σ\(z¯\)\>σ¯′\\sigma\(z\)\\geq\\sigma\(\\underline\{z\}\)\>\\overline\{\\sigma\}^\{\\prime\}for everyzz; in both casesS=∅S=\\emptyset\. Otherwiseσ\(z¯\)≤σ¯′\\sigma\(\\underline\{z\}\)\\leq\\overline\{\\sigma\}^\{\\prime\}andσ\(z¯\)≥σ¯′\\sigma\(\\overline\{z\}\)\\geq\\underline\{\\sigma\}^\{\\prime\}\. The set\{z:σ\(z\)≥σ¯′\}\\\{z:\\sigma\(z\)\\geq\\underline\{\\sigma\}^\{\\prime\}\\\}is a closed upper set of the interval and\{z:σ\(z\)≤σ¯′\}\\\{z:\\sigma\(z\)\\leq\\overline\{\\sigma\}^\{\\prime\}\\\}a closed lower set, soSSis their intersection, a closed interval, and it is non\-empty because by continuity somezzhasσ\(z\)∈\[σ¯′,σ¯′\]\\sigma\(z\)\\in\[\\underline\{\\sigma\}^\{\\prime\},\\overline\{\\sigma\}^\{\\prime\}\]\.
*Item 2\.*Ifσ\(z¯\)≥σ¯′\\sigma\(\\underline\{z\}\)\\geq\\underline\{\\sigma\}^\{\\prime\}, thenz¯′=z¯\\underline\{z\}^\{\\prime\}=\\underline\{z\}is below every element ofSS\. Otherwiseσ\(z¯\)<σ¯′≤σ\(z¯\)\\sigma\(\\underline\{z\}\)<\\underline\{\\sigma\}^\{\\prime\}\\leq\\sigma\(\\overline\{z\}\), so the starting pair satisfies the property\. A pair withσ\(a\)<σ¯′≤σ\(b\)\\sigma\(a\)<\\underline\{\\sigma\}^\{\\prime\}\\leq\\sigma\(b\)has one half with the same property:\[a,m\]\[a,m\]ifσ\(m\)≥σ¯′\\sigma\(m\)\\geq\\underline\{\\sigma\}^\{\\prime\}and\[m,b\]\[m,b\]otherwise\. Everyz∈Sz\\in Ssatisfiesσ\(z\)≥σ¯′\>σ\(a\)\\sigma\(z\)\\geq\\underline\{\\sigma\}^\{\\prime\}\>\\sigma\(a\), hencez\>az\>abecauseσ\\sigmais non\-decreasing\. Soz¯′=a\\underline\{z\}^\{\\prime\}=ais below every element ofSSafter any number of halvings, anda≥z¯a\\geq\\underline\{z\}\. The smallest element ofSSlies in\(a,b\]\(a,b\], so its distance toaais at mostb−ab\-a, which halves at every step\.
*Item 3*is symmetric with the propertyσ\(a\)≤σ¯′<σ\(b\)\\sigma\(a\)\\leq\\overline\{\\sigma\}^\{\\prime\}<\\sigma\(b\): everyz∈Sz\\in Ssatisfiesσ\(z\)≤σ¯′<σ\(b\)\\sigma\(z\)\\leq\\overline\{\\sigma\}^\{\\prime\}<\\sigma\(b\), hencez<bz<b, andb≤z¯b\\leq\\overline\{z\}\.
Both ends therefore satisfyz¯≤z¯′≤z≤z¯′≤z¯\\underline\{z\}\\leq\\underline\{z\}^\{\\prime\}\\leq z\\leq\\overline\{z\}^\{\\prime\}\\leq\\overline\{z\}for everyz∈Sz\\in S, which is the claim\. The non\-increasing case follows by applying the lemma to−σ\-\\sigmaand\[−σ¯′,−σ¯′\]\[\-\\overline\{\\sigma\}^\{\\prime\},\-\\underline\{\\sigma\}^\{\\prime\}\], sinceσ\(z\)∈\[σ¯′,σ¯′\]\\sigma\(z\)\\in\[\\underline\{\\sigma\}^\{\\prime\},\\overline\{\\sigma\}^\{\\prime\}\]if and only if−σ\(z\)∈\[−σ¯′,−σ¯′\]\-\\sigma\(z\)\\in\[\-\\overline\{\\sigma\}^\{\\prime\},\-\\underline\{\\sigma\}^\{\\prime\}\]\. ∎
### B\.4\.Soundness of Tightening
###### Proof of Theorem[5\.3](https://arxiv.org/html/2611.22083#S5.Thmtheorem3)\.
Letx∈ℛ\(P\)∩BRSf\(𝒴\)x\\in\\mathcal\{R\}\(P\)\\cap\\BRS\_\{f\}\(\\mathcal\{Y\}\)\. By Lemma[A\.1](https://arxiv.org/html/2611.22083#A1.Thmtheorem1), all its pre\-activations and post\-activations lie in the bounds ofℬP\\mathcal\{B\}\_\{P\}, andHf\(x\)=HWR\+1σ\(R\)\(z\(R\)\(x\)\)\+HbR\+1≤hHf\(x\)=HW\_\{R\+1\}\\sigma^\{\(R\)\}\(z^\{\(R\)\}\(x\)\)\+Hb\_\{R\+1\}\\leq h\. By Lemma[5\.1](https://arxiv.org/html/2611.22083#S5.Thmtheorem1),σ\(R\)\(z\(R\)\(x\)\)\\sigma^\{\(R\)\}\(z^\{\(R\)\}\(x\)\)lies in the contracted interval vector of line 1\. Inductively, ifσ\(r\)\(z\(r\)\(x\)\)\\sigma^\{\(r\)\}\(z^\{\(r\)\}\(x\)\)lies in its contracted interval vector, thenzj\(r\)\(x\)z^\{\(r\)\}\_\{j\}\(x\)lies in the interval of Lemma[5\.2](https://arxiv.org/html/2611.22083#S5.Thmtheorem2)for every certified neuron, and in its unchanged interval otherwise\. Lemma[5\.1](https://arxiv.org/html/2611.22083#S5.Thmtheorem1)applied toz\(r\)\(x\)=Wrσ\(r−1\)\(z\(r−1\)\(x\)\)\+brz^\{\(r\)\}\(x\)=W\_\{r\}\\sigma^\{\(r\-1\)\}\(z^\{\(r\-1\)\}\(x\)\)\+b\_\{r\}then placesσ\(r−1\)\(z\(r−1\)\(x\)\)\\sigma^\{\(r\-1\)\}\(z^\{\(r\-1\)\}\(x\)\)in its contracted interval vector\. Finally,Ax\+clo=L\(x\)≤Hf\(x\)≤hAx\+c\_\{\\mathrm\{lo\}\}=L\(x\)\\leq Hf\(x\)\\leq hby Theorem[4\.2](https://arxiv.org/html/2611.22083#S4.Thmtheorem2), so the contraction of line 7 keepsxx\. Hencex∈ℛ\(P′\)x\\in\\mathcal\{R\}\(P^\{\\prime\}\), and no interval can become empty while such anxxexists\. The inclusionℛ\(P′\)⊆ℛ\(P\)\\mathcal\{R\}\(P^\{\\prime\}\)\\subseteq\\mathcal\{R\}\(P\)holds because every bound only shrinks\. ∎
### B\.5\.Classification and Parts
###### Proof of Theorem[5\.4](https://arxiv.org/html/2611.22083#S5.Thmtheorem4)\.
The row boundρ¯i\\underline\{\\rho\}\_\{i\}\(ρ¯i\\overline\{\\rho\}\_\{i\}\) is the largest lower \(smallest upper\) bound on\(Hf\(x\)\)i\(Hf\(x\)\)\_\{i\}among the partial bounds of the back\-substitution of Theorem[4\.2](https://arxiv.org/html/2611.22083#S4.Thmtheorem2), each evaluated over the interval of its variable\. Each partial bound is linear in a quantity that stays in its interval onℛ\(P\)\\mathcal\{R\}\(P\)by Lemma[A\.1](https://arxiv.org/html/2611.22083#A1.Thmtheorem1), so the row bounds are valid onℛ\(P\)\\mathcal\{R\}\(P\)\. Items 1 and 2 follow from Lemma[A\.1](https://arxiv.org/html/2611.22083#A1.Thmtheorem1)and from this validity\. For item 3, ifx∈ℛ\(P\)x\\in\\mathcal\{R\}\(P\)andU\(x\)≤hU\(x\)\\leq h, thenHf\(x\)≤U\(x\)≤hHf\(x\)\\leq U\(x\)\\leq hby Theorem[4\.2](https://arxiv.org/html/2611.22083#S4.Thmtheorem2)\. For item 4, ifx∈ℛ\(P\)∩BRSf\(𝒴\)x\\in\\mathcal\{R\}\(P\)\\cap\\BRS\_\{f\}\(\\mathcal\{Y\}\), thenL\(x\)≤Hf\(x\)≤hL\(x\)\\leq Hf\(x\)\\leq h\. The polytopeO^\(P\)\\hat\{O\}\(P\)drops the constraints of layersr≥2r\\geq 2fromℛ\(P\)\\mathcal\{R\}\(P\), which can only enlarge the set\. Items 3 and 4 also hold withℛ\(P\)\\mathcal\{R\}\(P\)replaced byℛ\(P′\)\\mathcal\{R\}\(P^\{\\prime\}\)for any patternP′P^\{\\prime\}withℛ\(P′\)⊆ℛ\(P\)\\mathcal\{R\}\(P^\{\\prime\}\)\\subseteq\\mathcal\{R\}\(P\), because the bounds of Theorem[4\.2](https://arxiv.org/html/2611.22083#S4.Thmtheorem2)hold onℛ\(P\)\\mathcal\{R\}\(P\)\. ∎
## Appendix CBranching
This appendix gives the shares of the input score, the volume estimates, the initial partition and the parallel rounds of Section[6](https://arxiv.org/html/2611.22083#S6)\. It states and proves Propositions[C\.1](https://arxiv.org/html/2611.22083#A3.Thmtheorem1)and[C\.2](https://arxiv.org/html/2611.22083#A3.Thmtheorem2), Lemma[C\.3](https://arxiv.org/html/2611.22083#A3.Thmtheorem3)and Theorem[C\.4](https://arxiv.org/html/2611.22083#A3.Thmtheorem4), which that section cites\.
### C\.1\.Shares of the Input Score
The input score of Section[6\.2](https://arxiv.org/html/2611.22083#S6.SS2)uses the shares
\(17\)S\(1\)ji=\|W1,ji\|hi\(X^′\)∑i′\|W1,ji′\|hi′\(X^′\),S\(r\)=N\(r\)S\(r−1\),Njj′\(r\)=\|Wr,jj′\|\(σ¯j′\(r−1\)−σ¯j′\(r−1\)\)∑j′′\|Wr,jj′′\|\(σ¯j′′\(r−1\)−σ¯j′′\(r−1\)\),\\begin\{gathered\}S^\{\(1\)\}\_\{ji\}=\\frac\{\|W\_\{1,ji\}\|\\,h\_\{i\}\(\\hat\{X\}^\{\\prime\}\)\}\{\\sum\_\{i^\{\\prime\}\}\|W\_\{1,ji^\{\\prime\}\}\|\\,h\_\{i^\{\\prime\}\}\(\\hat\{X\}^\{\\prime\}\)\},\\qquad S^\{\(r\)\}=N^\{\(r\)\}S^\{\(r\-1\)\},\\\\ N^\{\(r\)\}\_\{jj^\{\\prime\}\}=\\frac\{\|W\_\{r,jj^\{\\prime\}\}\|\\,\(\\overline\{\\sigma\}^\{\(r\-1\)\}\_\{j^\{\\prime\}\}\-\\underline\{\\sigma\}^\{\(r\-1\)\}\_\{j^\{\\prime\}\}\)\}\{\\sum\_\{j^\{\\prime\\prime\}\}\|W\_\{r,jj^\{\\prime\\prime\}\}\|\\,\(\\overline\{\\sigma\}^\{\(r\-1\)\}\_\{j^\{\\prime\\prime\}\}\-\\underline\{\\sigma\}^\{\(r\-1\)\}\_\{j^\{\\prime\\prime\}\}\)\},\\end\{gathered\}whereSji\(r\)S^\{\(r\)\}\_\{ji\}is the share of the width ofzj\(r\)z^\{\(r\)\}\_\{j\}that is due toxix\_\{i\}, andN\(r\)N^\{\(r\)\}is the matrix of the shares of the post\-activation widths of layerr−1r\-1in the width of each pre\-activation of layerrr\. Every row ofS\(1\)S^\{\(1\)\}and ofN\(r\)N^\{\(r\)\}sums to one, so for each neuron the sharesSji\(r\)S^\{\(r\)\}\_\{ji\}of all input dimensions sum to one\. WithSji\(r\)=1S^\{\(r\)\}\_\{ji\}=1the input score of a neuron equals its neuron score34θrj\\tfrac\{3\}\{4\}\\theta\_\{rj\}\.
### C\.2\.Monotone Splits
###### Proposition C\.1 \(Monotone splits\)\.
Unless it is constant, the activationσj\(r\)\\sigma^\{\(r\)\}\_\{j\}has at mostn−1n\-1critical points\. Suppose that every critical point ofσj\(r\)\\sigma^\{\(r\)\}\_\{j\}in\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]is simple\. Then for every sufficiently fine subdivision of\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]whose split points include these critical points, the monotonicity certificate of Lemma[B\.1](https://arxiv.org/html/2611.22083#A2.Thmtheorem1)holds on every piece\.
The proposition is a statement about the split points\. It does not claim that the selection rule produces a fine subdivision\.
###### Proof of Proposition[C\.1](https://arxiv.org/html/2611.22083#A3.Thmtheorem1)\.
The polynomial\(σj\(r\)\)′\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\}has degreen−1n\-1, so it has at mostn−1n\-1roots unless it is identically zero\. If it is identically zero,σj\(r\)\\sigma^\{\(r\)\}\_\{j\}is constant and all Bernstein coefficients are equal\. Consider a piece\[c,c\+w\]\[c,c\+w\]of the subdivision\.
Suppose that the piece starts at a simple rootccof\(σj\(r\)\)′\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\}\. The Bernstein coefficients of\(σj\(r\)\)′\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\}on the piece equal its values at the grid pointsc\+wi/\(n−1\)c\+w\\,i/\(n\-1\)up to𝒪\(w2\)\\mathcal\{O\}\(w^\{2\}\), and these values are\(σj\(r\)\)′′\(c\)wi/\(n−1\)\+𝒪\(w2\)\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\\prime\}\(c\)\\,w\\,i/\(n\-1\)\+\\mathcal\{O\}\(w^\{2\}\)\. The first Bernstein coefficient equals\(σj\(r\)\)′\(c\)=0\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\}\(c\)=0\. Since\(σj\(r\)\)′′\(c\)≠0\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\\prime\}\(c\)\\neq 0, all other Bernstein coefficients have the sign of\(σj\(r\)\)′′\(c\)\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\\prime\}\(c\)for smallww\. By \(P3\), the differences of the Bernstein coefficients ofσj\(r\)\\sigma^\{\(r\)\}\_\{j\}on the piece are proportional to the Bernstein coefficients of\(σj\(r\)\)′\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\}, so they do not change sign\.
A piece that ends at a root is symmetric\. A piece that contains no root has\|\(σj\(r\)\)′\|\|\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\}\|bounded away from zero, and the Bernstein coefficients of\(σj\(r\)\)′\(\\sigma^\{\(r\)\}\_\{j\}\)^\{\\prime\}on a fine piece converge to its values uniformly, so they share one sign\. For a sufficiently fine subdivision, each piece falls into one of these cases\. ∎
### C\.3\.Volume Estimates and Queue Order
The estimated volume of a pattern is the estimated share of the input box𝒳\\mathcal\{X\}that its region covers\. Letninn\_\{\\mathrm\{in\}\}of theMMsamples ofX^′\\hat\{X\}^\{\\prime\}lie inℛ\(P′\)\\mathcal\{R\}\(P^\{\\prime\}\)andnCn\_\{C\}in the region of childCC\. The estimated volumes relative to𝒳\\mathcal\{X\}are
\(18\)m^\(P′\)=vol\(X^′\)vol\(𝒳\)⋅max\(nin,1\)M\+1,m^\(C\)=m^\(P′\)⋅nC\+12nin\+1\.\\hat\{m\}\(P^\{\\prime\}\)=\\frac\{\\vol\(\\hat\{X\}^\{\\prime\}\)\}\{\\vol\(\\mathcal\{X\}\)\}\\cdot\\frac\{\\max\(n\_\{\\mathrm\{in\}\},1\)\}\{M\+1\},\\qquad\\hat\{m\}\(C\)=\\hat\{m\}\(P^\{\\prime\}\)\\cdot\\frac\{n\_\{C\}\+\\tfrac\{1\}\{2\}\}\{n\_\{\\mathrm\{in\}\}\+1\}\.A tail of a joint split receives the Gaussian tail probabilityη=Φ\(−κ\)≈3\.2⋅10−5\\eta=\\Phi\(\-\\kappa\)\\approx 3\.2\\cdot 10^\{\-5\}of its parent, withΦ\\Phithe standard normal distribution function, and the central part receives1−2η1\-2\\eta\. These values replace the counts of \([18](https://arxiv.org/html/2611.22083#A3.E18)\), so the children \([15](https://arxiv.org/html/2611.22083#S6.E15)\) have the volumes
\(19\)m^\(Tt±\)=m^\(P′\)η\(1−2η\)t−1,m^\(K\)=m^\(P′\)\(1−2η\)\|S\|\.\\hat\{m\}\(T\_\{t\}^\{\\pm\}\)=\\hat\{m\}\(P^\{\\prime\}\)\\,\\eta\\,\(1\-2\\eta\)^\{t\-1\},\\qquad\\hat\{m\}\(K\)=\\hat\{m\}\(P^\{\\prime\}\)\\,\(1\-2\\eta\)^\{\|S\|\}\.The patterns of the initial partition have these volumes withm^\(P′\)=1\\hat\{m\}\(P^\{\\prime\}\)=1\. The estimates are heuristic and only order the priority queue\. A round takes at mostBBof the pending patterns of largest estimated volume, and only those with estimated volume at leastγ=10−3\\gamma=10^\{\-3\}times the largest\. The pattern of largest estimated volume is always taken\.
### C\.4\.Concentration
###### Proposition C\.2 \(Concentration\)\.
Letxxbe uniform on a boxX^\\hat\{X\}, letz=w⊤x\+bz=w^\{\\top\}x\+b, and letvi=\|wi\|hi\(X^\)v\_\{i\}=\|w\_\{i\}\|\\,h\_\{i\}\(\\hat\{X\}\)\. The interval ofzzoverX^\\hat\{X\}has width‖v‖1\\\|v\\\|\_\{1\}, andzzhas standard deviation‖v‖2/12\\\|v\\\|\_\{2\}/\\sqrt\{12\}\. Their ratio lies in\[12,12d\]\[\\sqrt\{12\},\\sqrt\{12d\}\]\.
###### Proof of Proposition[C\.2](https://arxiv.org/html/2611.22083#A3.Thmtheorem2)\.
The coordinates are independent and uniform, so the variance ofwixiw\_\{i\}x\_\{i\}isvi2/12v\_\{i\}^\{2\}/12, and the variance ofzzis‖v‖22/12\\\|v\\\|\_\{2\}^\{2\}/12\. The interval width is∑ivi=‖v‖1\\sum\_\{i\}v\_\{i\}=\\\|v\\\|\_\{1\}\. The bounds follow from‖v‖2≤‖v‖1≤d‖v‖2\\\|v\\\|\_\{2\}\\leq\\\|v\\\|\_\{1\}\\leq\\sqrt\{d\}\\,\\\|v\\\|\_\{2\}\. ∎
Eligibility is typical in high dimension\. For weights with i\.i\.d\. Gaussian entries and equal edge lengths,‖v‖1/‖v‖2≈2d/π\\\|v\\\|\_\{1\}/\\\|v\\\|\_\{2\}\\approx\\sqrt\{2d/\\pi\}\. The ratio of Proposition[C\.2](https://arxiv.org/html/2611.22083#A3.Thmtheorem2)is then about2\.76d2\.76\\sqrt\{d\}\. By the central limit theorem,zzis approximately Gaussian\. The interval\[μ−4ς,μ\+4ς\]\[\\mu\-4\\varsigma,\\mu\+4\\varsigma\], with meanμ\\muand standard deviationς\\varsigma, holds all but about6⋅10−56\\cdot 10^\{\-5\}of the volume\. It covers a fraction of about2\.9/d2\.9/\\sqrt\{d\}of the interval ofzz, which is about0\.090\.09ford=1024d=1024\. A bisection only halves such an interval, so its children stay much wider than the part that holds the volume\. A restriction ofzzto\[μ−4ς,μ\+4ς\]\[\\mu\-4\\varsigma,\\mu\+4\\varsigma\]shrinks the interval by a factor of about2\.9/d2\.9/\\sqrt\{d\}and moves almost no volume into the tails\. For a first\-layer neuron and up to sampling error, the proposition shows that eligibility is possible only if12d\>2κ/ω\\sqrt\{12d\}\>2\\kappa/\\omega, that isd\>21d\>21forκ=4\\kappa=4andω=1/2\\omega=1/2\. Deeper neurons are not covered by the proposition, and the test is applied to them as well\.
### C\.5\.Joint Split
###### Lemma C\.3 \(Joint split\)\.
The at most2\|S\|\+12\|S\|\+1children \([15](https://arxiv.org/html/2611.22083#S6.E15)\) coverℛ\(P′\)\\mathcal\{R\}\(P^\{\\prime\}\)\. Two different children intersect only in a set on which some pre\-activationztz\_\{t\}equals an endpoint ofCtC\_\{t\}\.
###### Proof of Lemma[C\.3](https://arxiv.org/html/2611.22083#A3.Thmtheorem3)\.
Letx∈ℛ\(P′\)x\\in\\mathcal\{R\}\(P^\{\\prime\}\)\. Ifzt\(x\)∈Ctz\_\{t\}\(x\)\\in C\_\{t\}for alltt, thenx∈Kx\\in K\. Otherwise letttbe the smallest index withzt\(x\)∉Ctz\_\{t\}\(x\)\\notin C\_\{t\}\. Thenzs\(x\)∈Csz\_\{s\}\(x\)\\in C\_\{s\}fors<ts<t, andzt\(x\)<c¯tz\_\{t\}\(x\)<\\underline\{c\}\_\{t\}orzt\(x\)\>c¯tz\_\{t\}\(x\)\>\\overline\{c\}\_\{t\}, sox∈Tt−x\\in T\_\{t\}^\{\-\}orx∈Tt\+x\\in T\_\{t\}^\{\+\}\. An omitted tail adds nothing: ifc¯t\\underline\{c\}\_\{t\}equals the lower end of the interval of neurontt, every input ofℛ\(P′\)\\mathcal\{R\}\(P^\{\\prime\}\)withzt≤c¯tz\_\{t\}\\leq\\underline\{c\}\_\{t\}haszt=c¯t∈Ctz\_\{t\}=\\underline\{c\}\_\{t\}\\in C\_\{t\}and lies in a later child, and the same holds at the upper end\. For the second claim, let two different children carry the indicest<t′t<t^\{\\prime\}, whereKKhas the index\|S\|\+1\|S\|\+1\. The child of indext′t^\{\\prime\}requireszt∈Ctz\_\{t\}\\in C\_\{t\}\. The child of indexttrequireszt≤c¯tz\_\{t\}\\leq\\underline\{c\}\_\{t\}orzt≥c¯tz\_\{t\}\\geq\\overline\{c\}\_\{t\}\. Both hold only ifztz\_\{t\}equals an endpoint ofCtC\_\{t\}\. The two tails of the same index meet only wherec¯t=c¯t\\underline\{c\}\_\{t\}=\\overline\{c\}\_\{t\}, which is also an endpoint\. ∎
### C\.6\.Initial Partition
Before the first round,BernBRSreplaces the root by a joint split of the first layer, with closed\-form statistics instead of samples\. For uniform inputs on𝒳\\mathcal\{X\}, the meanμj\\mu\_\{j\}ofzj\(1\)z^\{\(1\)\}\_\{j\}is its value at the centre of𝒳\\mathcal\{X\}, and its variance isςj2=∑iW1,ji2hi\(𝒳\)2/12\\varsigma\_\{j\}^\{2\}=\\sum\_\{i\}W\_\{1,ji\}^\{2\}h\_\{i\}\(\\mathcal\{X\}\)^\{2\}/12\(Proposition[C\.2](https://arxiv.org/html/2611.22083#A3.Thmtheorem2)\)\. Letj1,…,jpj\_\{1\},\\dots,j\_\{p\}be the neurons whose central interval\[μj−κςj,μj\+κςj\]\[\\mu\_\{j\}\-\\kappa\\varsigma\_\{j\},\\mu\_\{j\}\+\\kappa\\varsigma\_\{j\}\]is narrower thanω\\omegatimes the range∑i\|W1,ji\|hi\(𝒳\)\\sum\_\{i\}\|W\_\{1,ji\}\|h\_\{i\}\(\\mathcal\{X\}\)ofzj\(1\)z^\{\(1\)\}\_\{j\}over𝒳\\mathcal\{X\}\. The joint split \([15](https://arxiv.org/html/2611.22083#S6.E15)\) with this set gives2p\+12p\+1patterns that cover the root, the*initial partition*\. Ifp=0p=0, the root is kept\.
### C\.7\.Parallel Rounds, Backends and Budget
The patterns of a round are processed independently of each other\. The batched PyTorch backend processes a round as one pass on the device, and the NumPy backend processes its patterns one by one\. With the same samples, the two backends make the same decisions up to floating\-point summation\. In the reported PyTorch runs the samples come from the PyTorch generator, so the search trees differ from those of the NumPy backend\. Algorithm[1](https://arxiv.org/html/2611.22083#alg1)processes at mostNNpatterns with splitting and then classifies the pending ones without splitting, in the order of largest estimated volume first\.
### C\.8\.Soundness ofBernBRS
The root pattern hasX^=𝒳\\hat\{X\}=\\mathcal\{X\}and intervalsZ^\(r\)\\hat\{Z\}^\{\(r\)\}that enclosez\(r\)\(𝒳\)z^\{\(r\)\}\(\\mathcal\{X\}\), so its region is𝒳\\mathcal\{X\}\.Collectadds an accepted region to bothℐ\\mathcal\{I\}and𝒪\\mathcal\{O\}, discards a pruned pattern, inserts the children of a split into𝒬\\mathcal\{Q\}, and adds the partsIIandOOof an undecided pattern toℐ\\mathcal\{I\}and𝒪\\mathcal\{O\}\.
###### Theorem C\.4 \(Soundness of BernBRS\)\.
BernBRSterminates\. It processes at mostN\+\(2p\+1\)\+2WΣNN\+\(2p\+1\)\+2W\_\{\\Sigma\}Npatterns, and at most2N2Nif the final classification is limited toNNpatterns, where2p\+12p\+1is the size of the initial partition \(Appendix[C\.6](https://arxiv.org/html/2611.22083#A3.SS6)\) andWΣW\_\{\\Sigma\}the number of hidden neurons\. At the start of every round,
\(20\)⋃ℐ⊆BRSf\(𝒴\)⊆⋃𝒪∪⋃P∈𝒬ℛ\(P\),\\bigcup\\mathcal\{I\}\\;\\subseteq\\;\\BRS\_\{f\}\(\\mathcal\{Y\}\)\\;\\subseteq\\;\\bigcup\\mathcal\{O\}\\,\\cup\\,\\bigcup\_\{P\\in\\mathcal\{Q\}\}\\mathcal\{R\}\(P\),where𝒬\\mathcal\{Q\}is the set of pending patterns, and the returned families satisfy \([7](https://arxiv.org/html/2611.22083#S2.E7)\)\.
Stopping after any round and adding the pending regions to𝒪\\mathcal\{O\}therefore yields a valid answer\. Every step is polynomial in the input dimension, the widths, the depth and the degree\. The cost that is exponential in the worst case is confined to the number of patterns\.
###### Proof of Theorem[C\.4](https://arxiv.org/html/2611.22083#A3.Thmtheorem4)\.
*Inner inclusion\.*Sets are added toℐ\\mathcal\{I\}only as accepted regions or as inner parts\. Both are contained inBRSf\(𝒴\)\\BRS\_\{f\}\(\\mathcal\{Y\}\)by Theorem[5\.4](https://arxiv.org/html/2611.22083#S5.Thmtheorem4), applied to the pattern for which the set was produced\. Explicit accepted regions are accepted on a superset of the pattern region, so the same theorem applies to them\.
*Outer inclusion\.*Initially𝒬\\mathcal\{Q\}holds the root, whose region is𝒳⊇BRSf\(𝒴\)\\mathcal\{X\}\\supseteq\\BRS\_\{f\}\(\\mathcal\{Y\}\)\. With the initial partition,𝒬\\mathcal\{Q\}holds2p\+12p\+1patterns that cover𝒳\\mathcal\{X\}\(Appendix[C\.6](https://arxiv.org/html/2611.22083#A3.SS6)and Lemma[C\.3](https://arxiv.org/html/2611.22083#A3.Thmtheorem3)\)\. When a patternPPis processed, the points ofℛ\(P\)∩BRSf\(𝒴\)\\mathcal\{R\}\(P\)\\cap\\BRS\_\{f\}\(\\mathcal\{Y\}\)remain covered\. IfPPis pruned, there are none \(Theorems[5\.3](https://arxiv.org/html/2611.22083#S5.Thmtheorem3)and[5\.4](https://arxiv.org/html/2611.22083#S5.Thmtheorem4)\)\. If it is accepted or undecided, they lie in the set added to𝒪\\mathcal\{O\}, by Theorem[5\.4](https://arxiv.org/html/2611.22083#S5.Thmtheorem4)applied to the contracted patternP′P^\{\\prime\}and byℛ\(P\)∩BRSf\(𝒴\)⊆ℛ\(P′\)\\mathcal\{R\}\(P\)\\cap\\BRS\_\{f\}\(\\mathcal\{Y\}\)\\subseteq\\mathcal\{R\}\(P^\{\\prime\}\)from Theorem[5\.3](https://arxiv.org/html/2611.22083#S5.Thmtheorem3)\. A pattern whose bounds are not finite is returned as its own region, which contains these points\. IfPPis split, its children coverℛ\(P′\)\\mathcal\{R\}\(P^\{\\prime\}\)\. A neuron split covers the split interval with two intervals\. A joint split coversℛ\(P′\)\\mathcal\{R\}\(P^\{\\prime\}\)with at most2\|S\|\+12\|S\|\+1children \(Lemma[C\.3](https://arxiv.org/html/2611.22083#A3.Thmtheorem3)\)\. An input split covers the box with two boxes\. All other constraints are those ofP′P^\{\\prime\}\.
*Termination\.*Every round of the refinement stage processes at least one pattern, because the pending pattern of largest estimated volume always passes the volume gate \(Appendix[C\.3](https://arxiv.org/html/2611.22083#A3.SS3)\), and the counter of processed patterns never exceedsNNin this stage\. The stage therefore ends after at mostNNprocessed patterns\. Each processed pattern is replaced by at most2WΣ\+12W\_\{\\Sigma\}\+1children, since\|S\|≤WΣ\|S\|\\leq W\_\{\\Sigma\}\. At most2p\+1\+2WΣN2p\+1\+2W\_\{\\Sigma\}Npatterns are pending at the end of the stage\. The final classification processes pending patterns without splitting and creates none, so it ends after a finite number of rounds\. If it is limited toNNpatterns, the remaining ones are added to𝒪\\mathcal\{O\}as their regions\. Then𝒬=∅\\mathcal\{Q\}=\\emptyset, and \([20](https://arxiv.org/html/2611.22083#A3.E20)\) is \([7](https://arxiv.org/html/2611.22083#S2.E7)\)\. ∎
## Appendix DSettings of the Runs
Table[3](https://arxiv.org/html/2611.22083#A4.T3)lists the experiments and the case studies\. The ratios of Section[7](https://arxiv.org/html/2611.22083#S7)are defined forvol\(BRSf\(𝒴\)\)\>0\\vol\(\\BRS\_\{f\}\(\\mathcal\{Y\}\)\)\>0\. The volumes are estimated on20,00020\{,\}000uniform samples of the input box\. Every run is checked on these samples\. No sampled input of the inner set lies outside the BRS, and no sampled input of the BRS lies outside the outer set\. All runs use the defaults of Sections[4](https://arxiv.org/html/2611.22083#S4)to[6](https://arxiv.org/html/2611.22083#S6)withM=4,096M=4\{,\}096volume samples,N=400N=400unless stated otherwise, and every pending pattern classified at the end\. The GPU is one NVIDIA A30, and TinyBERT and the two\-input networks run on CPU cores\.
Table 3\.The experiments and the case studies\. Trained networks have degree99\. A run is one execution ofBernBRSat one budget\.
## Appendix EImage Classifiers
This appendix gives the training of Bernstein networks 1 and 2 of Experiment 2\. On MNIST\([LeCun et al\., 1998](https://arxiv.org/html/2611.22083#bib.bib16)\), GTSRB\([Stallkamp et al\., 2012](https://arxiv.org/html/2611.22083#bib.bib31)\)and CIFAR\-10\([Krizhevsky, 2009](https://arxiv.org/html/2611.22083#bib.bib15)\), inputs are flattened and scaled to\[0,1\]\[0,1\], without data augmentation\. GTSRB images are cropped to the sign and resized to32×3232\\times 32\. The networks have no batch normalization\. Every hidden neuron has its own learned Bernstein activation of degreen=9n=9on the bounds\[−5,5\]\[\-5,5\]\.
Both networks use AdamW with weight decay10−410^\{\-4\}, a one\-cycle learning rate with peak10−310^\{\-3\}and 10 % warm\-up, 40 epochs, batch size 128 and seed 0\. Before the first step, each linear layer is rescaled so that its pre\-activations have standard deviation 1\.5 on 2,000 training images\. The penalty5∑rmeanjmax\(\|zrj\|−5,0\)25\\sum\_\{r\}\\operatorname\{mean\}\_\{j\}\\max\(\|z\_\{rj\}\|\-5,0\)^\{2\}on the pre\-activationszrjz\_\{rj\}of hidden layerrrkeeps the training data inside the bounds\.
Bernstein network 1 uses bi\-Lipschitz training with the cross\-entropy loss\. Each square weight matrix, between hidden layers, is parametrized asW=diag\(s\)QW=\\operatorname\{diag\}\(s\)\\,Q, withQQorthogonal andsj=gexp\(12ln4tanhtj\)s\_\{j\}=g\\exp\(\\tfrac\{1\}\{2\}\\ln 4\\,\\tanh t\_\{j\}\), so its condition number is at most 4\. Neighbouring Bernstein coefficients satisfyck\+1−ck∈\[0\.25/n,4/n\]c\_\{k\+1\}\-c\_\{k\}\\in\[0\.25/n,4/n\], so every activation is increasing, with slope between 0\.025 and 0\.4\. The weight matrices from the inputs and to the outputs stay free\.
Bernstein network 2 uses certified training\. It minimizesαLclean\+\(1−α\)Lrobust\\alpha L\_\{\\mathrm\{clean\}\}\+\(1\-\\alpha\)L\_\{\\mathrm\{robust\}\}as in DeepBern\-Nets\([Khedr and Shoukry, 2024](https://arxiv.org/html/2611.22083#bib.bib13)\), with the penalty\. The termLrobustL\_\{\\mathrm\{robust\}\}is the cross\-entropy of the worst\-case logits, from interval bound propagation\([Gowal et al\., 2019](https://arxiv.org/html/2611.22083#bib.bib7)\)over the box of radiusε\\varepsilonaround each training input\. Once the robust term starts,α\\alphafalls linearly from 0\.9 towards 0 over 14 epochs, down to its floor\. Table[4](https://arxiv.org/html/2611.22083#A5.T4)gives the rule forε\\varepsilon\. A ramp raises it linearly to its target over the same 14 epochs\. The adaptive rule starts at one tenth of the target and, after each epoch, multipliesε\\varepsilonby 1\.25 if the certified accuracy on the first 2,000 test images is at least 0\.8, and by 0\.8 otherwise, between one hundredth of the target and the target\.
Table 4\.Recipes of Bernstein network 2\. Floor: the smallestα\\alpha\. Robust from: the first epoch with a robust loss\. Kept from: the first epoch that may be kept as the final network\.Every network keeps the epoch with the best test accuracy among the eligible ones, given in Table[4](https://arxiv.org/html/2611.22083#A5.T4)for Bernstein network 2\. For Bernstein network 1 these are all epochs on MNIST, except from epoch 16 at width 500, and the epochs from 16 on for GTSRB and CIFAR\-10\. The selection uses the test set, so the test accuracies are slightly optimistic\.
## Appendix FCase Study 1: A Hybrid Dynamical Control System
This appendix gives the exact merge of the loop into the network form, the training of the controller, the plant, the runs and the settings of Case Study 1, and frames of one fall\.
### F\.1\.Exact Merge of the Closed Loop
The closed loop is merged, without training, into the form of Definition[2\.1](https://arxiv.org/html/2611.22083#S2.Thmtheorem1)\. The merged network equals the loop on the input box, so its certificates hold for the loop\. Letxt∈ℝdx\_\{t\}\\in\\mathbb\{R\}^\{d\}be the state\. A Bernstein controllerπ\\piwithRπR\_\{\\pi\}hidden layers acts on an affine, step\-dependent plant \(for example a linearization along a nominal trajectory\),
\(21\)xt\+1=Ft\(xt\)=Atxt\+Btclip\(π\(xt\),−1,1\)\+ct,x\_\{t\+1\}=F\_\{t\}\(x\_\{t\}\)=A\_\{t\}x\_\{t\}\+B\_\{t\}\\clip\\big\(\\pi\(x\_\{t\}\),\-1,1\\big\)\+c\_\{t\},whereAtA\_\{t\},BtB\_\{t\},ctc\_\{t\}are the matrices and offset of steptt\. For a horizonKKtheKK\-step backward reachable set isBRSK\(𝒴\)=\{x0∈𝒳:FK−1∘⋯∘F0\(x0\)∈𝒴\}\\BRS^\{K\}\(\\mathcal\{Y\}\)=\\\{x\_\{0\}\\in\\mathcal\{X\}:F\_\{K\-1\}\\circ\\dots\\circ F\_\{0\}\(x\_\{0\}\)\\in\\mathcal\{Y\}\\\}, with the target𝒴\\mathcal\{Y\}on the last state\.
In the merge, each hidden layer holds the controller’s neurons andddcopy neurons that carry the state\. A clip layer of identity neurons \(Lemma[F\.1](https://arxiv.org/html/2611.22083#A6.Thmtheorem1)\) with bounds\[−1,1\]\[\-1,1\]followsπ\\piand represents the action limits of the plant, and each plant step is one affine map composed with the next controller layer\. One step usesRπ\+1R\_\{\\pi\}\+1activation layers, and the merged networkfKf\_\{K\}mapsx0x\_\{0\}toxKx\_\{K\}\. The copy neurons receive their bounds from interval bounds over𝒳\\mathcal\{X\}, widened on each side by the width of the interval\.
###### Lemma F\.1 \(Identity neuron\)\.
Let neuron\(r,j\)\(r,j\)have bounds\[ℓ,u\]\[\\ell,u\],ℓ<u\\ell<u, and Bernstein coefficients
\(22\)ci=ℓ\+\(u−ℓ\)i/n,i=0,…,n\.c\_\{i\}=\\ell\+\(u\-\\ell\)\\,i/n,\\quad i=0,\\dots,n\.Thenσj\(r\)\(z\)=z\\sigma^\{\(r\)\}\_\{j\}\(z\)=zon\[ℓ,u\]\[\\ell,u\]\. On a pattern with pre\-activation interval\[z¯,z¯\]⊆\[ℓ,u\]\[\\underline\{z\},\\overline\{z\}\]\\subseteq\[\\ell,u\], the neuron is certified non\-decreasing, its secant slope is11, its relaxation width isβj\(r\)=0\\beta^\{\(r\)\}\_\{j\}=0, its contribution to every gap is00so that branching never splits it, and its inverse on the interval is exact\.
###### Proof of Lemma[F\.1](https://arxiv.org/html/2611.22083#A6.Thmtheorem1)\.
By \(P4\) the polynomial with Bernstein coefficients \([22](https://arxiv.org/html/2611.22083#A6.E22)\) on\[ℓ,u\]\[\\ell,u\]isz↦zz\\mapsto z\. On\[z¯,z¯\]\[\\underline\{z\},\\overline\{z\}\]the Bernstein coefficients areci′=z¯\+\(z¯−z¯\)i/nc^\{\\prime\}\_\{i\}=\\underline\{z\}\+\(\\overline\{z\}\-\\underline\{z\}\)\\,i/nby \(P2\) and \(P4\)\. They are non\-decreasing, so the neuron is certified non\-decreasing by Lemma[B\.1](https://arxiv.org/html/2611.22083#A2.Thmtheorem1)\. The secant slope is\(cn′−c0′\)/\(z¯−z¯\)=1\(c^\{\\prime\}\_\{n\}\-c^\{\\prime\}\_\{0\}\)/\(\\overline\{z\}\-\\underline\{z\}\)=1, and the offsets of Lemma[4\.1](https://arxiv.org/html/2611.22083#S4.Thmtheorem1)areei=ci′−z¯−\(z¯−z¯\)i/n=0e\_\{i\}=c^\{\\prime\}\_\{i\}\-\\underline\{z\}\-\(\\overline\{z\}\-\\underline\{z\}\)\\,i/n=0, so its relaxation width is00\. By the gap identity \([14](https://arxiv.org/html/2611.22083#S4.E14)\), the contribution of a neuron to the gap of a row is the magnitude of its back\-substituted coefficient times its relaxation width, so it is00\. A neuron split is scored by this contribution \(Section[6\.2](https://arxiv.org/html/2611.22083#S6.SS2)\), so branching never splits it\. The inverse is exact becauseσj\(r\)\(z\)=z\\sigma^\{\(r\)\}\_\{j\}\(z\)=zon the interval\. ∎
###### Proposition F\.2 \(Exact merge of the closed loop\)\.
Let every copy neuron have bounds containing the interval bounds over𝒳\\mathcal\{X\}of the coordinate it carries, and let every action stay within\[−1,1\]\[\-1,1\]on𝒳\\mathcal\{X\}\. Then:
1. \(1\)fK\(x0\)=FK−1∘⋯∘F0\(x0\)f\_\{K\}\(x\_\{0\}\)=F\_\{K\-1\}\\circ\\dots\\circ F\_\{0\}\(x\_\{0\}\)for everyx0∈𝒳x\_\{0\}\\in\\mathcal\{X\}, hence\{x0∈𝒳:fK\(x0\)∈𝒴\}=BRSK\(𝒴\)\\\{x\_\{0\}\\in\\mathcal\{X\}:f\_\{K\}\(x\_\{0\}\)\\in\\mathcal\{Y\}\\\}=\\BRS^\{K\}\(\\mathcal\{Y\}\);
2. \(2\)every copy neuron has relaxation width00on each pattern inside its bounds, so it is never split\.
The guarantee covers the loop given to the solver\.
###### Proof of Proposition[F\.2](https://arxiv.org/html/2611.22083#A6.Thmtheorem2)\.
\(1\) Copy neurons output their input for everyx0∈𝒳x\_\{0\}\\in\\mathcal\{X\}\(Lemma[F\.1](https://arxiv.org/html/2611.22083#A6.Thmtheorem1)\)\. The controller’s neurons receive the same inputs as inπ\\pi\. The clip layer outputs the action, which equalsclip\(π\(xt\),−1,1\)\\clip\(\\pi\(x\_\{t\}\),\-1,1\)because the action stays within\[−1,1\]\[\-1,1\]\. The composed affine map equals the plant step followed by the first controller layer, since composition of affine maps is affine and associative\. Induction overttgivesfK=FK−1∘⋯∘F0f\_\{K\}=F\_\{K\-1\}\\circ\\dots\\circ F\_\{0\}\. \(2\) This follows from Lemma[F\.1](https://arxiv.org/html/2611.22083#A6.Thmtheorem1)\. ∎
### F\.2\.The Controller and Its Training
The verified network is the trained controller itself, and no teacher is distilled into it\. It has 17 inputs, one hidden layer of 128 units, 6 outputs and Bernstein activations of degree 9\. Proximal policy optimization\([Schulman et al\., 2017](https://arxiv.org/html/2611.22083#bib.bib28)\)in Stable\-Baselines3\([Raffin et al\., 2021](https://arxiv.org/html/2611.22083#bib.bib23)\)trains it on the HalfCheetah\-v4 environment of Gymnasium\([Towers et al\., 2025](https://arxiv.org/html/2611.22083#bib.bib33)\), with Bernstein layers in place of hyperbolic tangent layers, for one million steps with one seed\. The actor outputs the mean action without a squashing function, and the simulator clips the action to\[−1,1\]\[\-1,1\], which is the clip layer of the merged network\. The critic is not verified and keeps the hyperbolic tangent network of the library\.
We adapt the certified training of DeepBern\-Nets\([Khedr and Shoukry, 2024](https://arxiv.org/html/2611.22083#bib.bib13)\)to PPO\. That training uses the cross\-entropy of the worst\-case logits, which needs class labels\. PPO has no labels, so our certified training adds a term on the width of the action interval to the loss of the library,
L=LPPO\+λt16\|ℳ\|∑o∈ℳ∑j=16\(u¯j\(o\)−u¯j\(o\)\)2\.L=L\_\{\\mathrm\{PPO\}\}\+\\lambda\_\{t\}\\,\\frac\{1\}\{6\|\\mathcal\{M\}\|\}\\sum\_\{o\\in\\mathcal\{M\}\}\\sum\_\{j=1\}^\{6\}\\big\(\\overline\{u\}\_\{j\}\(o\)\-\\underline\{u\}\_\{j\}\(o\)\\big\)^\{2\}\.Hereℳ\\mathcal\{M\}is the mini\-batch, and\[u¯j\(o\),u¯j\(o\)\]\[\\underline\{u\}\_\{j\}\(o\),\\overline\{u\}\_\{j\}\(o\)\]is the interval of the mean actionjjover the box of radiusϵt\\epsilon\_\{t\}around the normalized observationoo, computed by interval bound propagation\. The radiusϵt\\epsilon\_\{t\}and the weightλt\\lambda\_\{t\}ramp linearly from zero to their final values of 0\.05 and 3 between 10% and 60% of the steps\. The radius is in standardized observation units\.
The running observation normalization is folded into the first affine layer at export, so that the exported network takes raw states\. During training the bounds of each neuron follow the observed range of its pre\-activation, which only grows, widened by 10 % of that range on each side\. The export only widens them, to contain the pre\-activations on the last 100,000 training observations and on 20 fresh episodes, plus 10 % of their range on each side\. In ten further fresh deterministic episodes, every pre\-activation lies inside the bounds of its neuron\.
The training uses a learning rate of10−410^\{\-4\}, rollouts of 512 steps, mini\-batches of 64, 20 epochs per update, a discount of 0\.98, a GAE parameter of 0\.92, a clip range of 0\.1, an entropy coefficient of4\.02×10−44\.02\\times 10^\{\-4\}, a value coefficient of 0\.581, a maximum gradient norm of 0\.8 and an initiallogσ\\log\\sigmaof−2\-2\. These settings start from the published configuration for HalfCheetah of the RL Baselines3 Zoo\([Raffin, 2020](https://arxiv.org/html/2611.22083#bib.bib22)\), and a sweep of nineteen runs sets the learning rate and the final weight\. The versions are Stable\-Baselines3 2\.3\.2, Gymnasium 0\.29\.1 and MuJoCo 3\.1\.6\. A controller has no test or certified accuracy, so we report its return, which is4,339±3864\{,\}339\\pm 386on 10 fresh episodes\. Its action half\-width is 0\.0455 at the final radius\.
Figure 6\.Frames of the logged fall of episode 11, with the pitch below each frame\. One step is 0\.05 s, and the camera follows the robot\. The frames run fromk=20k=20to the target stepEE, and the last frame lies past the target\.
### F\.3\.Plant, Runs and Settings
Central finite differences of the whole simulator step giveAtA\_\{t\},BtB\_\{t\}andctc\_\{t\}of \([21](https://arxiv.org/html/2611.22083#A6.E21)\) along a closed\-loop path\. WithRπ=1R\_\{\\pi\}=1, one step gives 2 activation layers, so the merged network has2k2kactivation layers, with 40 layers and 3,360 units on 17 inputs atk=20k=20\. Each trajectory has one linearization from stepE−20E\-20, and the networks of one trajectory share their tails\.
Table[5](https://arxiv.org/html/2611.22083#A6.T5)lists the five falls that we analyze\. The linearization path of episode 49 departs from the logged states by up to 1\.6 half\-widths of the thin box, while the other four stay within 0\.04\.
Table 5\.The five falls: the episode, the target stepEE, the twenty start steps and the logged pitch atEE\.Each run takes a box around the logged state at its start step, with the half\-widths of Table[6](https://arxiv.org/html/2611.22083#A6.T6), whereSmS\_\{m\}ismmtimes the base half\-widthS1S\_\{1\}\. The base half\-widths are representative sensor errors, chosen and not measured on this simulator\. Table[7](https://arxiv.org/html/2611.22083#A6.T7)gives the scale of each coordinate in the wide box and in the thin box\. No error enters the loop at later steps\.
Table 6\.Half\-widths per group of state coordinates, rounded within each group\.Table 7\.The scale of each group of state coordinates in the two boxes, with the half\-widths of Table[6](https://arxiv.org/html/2611.22083#A6.T6)\. Bold: the coordinates atS16S\_\{16\}in both boxes\.Algorithm[1](https://arxiv.org/html/2611.22083#alg1)processes at mostN=2,000N=2\{,\}000patterns with splitting and then classifies every pending pattern, so the number of processed patterns can exceed2N2N\. Its median is 3,898 and its maximum is 20,211\. The other settings areB=64B=64,J=2J=2,M=4,096M=4\{,\}096,φ=0\.8\\varphi=0\.8,κ=4\\kappa=4,ω=0\.5\\omega=0\.5and the initial partition, in PyTorch with double precision on one A30 GPU per job\. The shares use 20,000 samples per box\. All runs took 12\.4 GPU hours\. Input splits make up 99\.6% of the splits, and joint splits occur in 19 of the 200 runs\.
All 200 runs pass the soundness check, forBernBRSand for the baseline: no sampled state of an inner set lies outside the true set, and no sampled state of the true set lies outside an outer set\. Copy neurons never leave their bounds in any run\. On 500 box points per run, the merged network and the loop differ by at most 0\.021, where states reach10610^\{6\}, a relative difference of2×10−82\\times 10^\{\-8\}\. This is consistent with floating\-point error amplified by the loop, and it was not tested further\.
The baseline is CROWN with guided input partitioning, on the same merged networks, targets, boxes and samples\. Its element budget doubles from one element up to two caps, 262,144 elements and 1,800 s per box\. Each box uses the last baseline run within the wall\-clock time ofBernBRSon that box\. On 6 boxes withk≤3k\\leq 3even the run of one element takes longer thanBernBRS, and that run is used\. Doubling leaves the baseline a median of 0\.57 of the time ofBernBRS\. The first run past that time adds 0\.007 to the inner share on average and overtakesBernBRSon none of 185 boxes\. The cap of elements applies on 8 boxes and the cap of time on 1\.
### F\.4\.One Logged Fall
Figure[6](https://arxiv.org/html/2611.22083#A6.F6)shows the fall of episode 11 in MuJoCo\. The robot tips forward over its head and lands on its back, and it stays there for the remaining 530 steps of the run\.
## Appendix GCase Study 2: Transformer
This appendix gives the training of the student network used in Case Study 2 and the setup of the runs\.
### G\.1\.Training
The teacher is TinyBERT\([Jiao et al\., 2020](https://arxiv.org/html/2611.22083#bib.bib11)\), a distilled BERT\([Devlin et al\., 2019](https://arxiv.org/html/2611.22083#bib.bib3)\)with 4 blocks of width 312 and 12 attention heads\. We fine\-tune it on SST\-2\([Socher et al\., 2013](https://arxiv.org/html/2611.22083#bib.bib30);[Wang et al\., 2019](https://arxiv.org/html/2611.22083#bib.bib36)\)for 5 epochs with AdamW\. The 872 development sentences serve as the test set, and the teacher reaches 88\.65 % on them\.
The student replaces the last block, the pooler and the classifier, while the first three blocks stay frozen\. It has three heads of width 26 with a monotone Bernstein gate of degree 9 in place of the softmax, an MLP of 300 Bernstein curves of degree 9, and the pooler’s dense map with 312 Bernstein curves of degree 9 in place of the tanh\. The classifier reads only the \[CLS\] row, so the student computes only that row\.
The student is initialized from the teacher\. Its loss is the distillation loss of Hinton et al\.\([Hinton et al\., 2015](https://arxiv.org/html/2611.22083#bib.bib8)\)with the cross\-entropy, a match of the \[CLS\] output, and a penalty that keeps each pre\-activation inside the domain of its curve\. Training runs for 30 epochs with AdamW, and we keep the epoch with the best agreement with the teacher on held\-out sentences\.
The student reaches 88\.53 % on the development sentences\.
### G\.2\.Setup
The free word of a sentence is the content word with the largest attention from the \[CLS\] token in the teacher’s last block\. With the other words fixed, the student is rewritten into a Bernstein network\. One word is free, so each attention score is affine in the word’s point and needs no squares\. Each product of a gate output and a value becomes a difference of two squares, and identity neurons \(Lemma[F\.1](https://arxiv.org/html/2611.22083#A6.Thmtheorem1)\) carry the free word’s point and the residual stream\. The rewritten network has four layers on 312 inputs, with 1,395 neurons in total, and it agrees with the student to at most5\.3⋅10−155\.3\\cdot 10^\{\-15\}on 2,000 uniform points, 200 corners and the centre of each box\.
For the word test, each of the 21,619 candidate words, the alphabetic whole words of the vocabulary that are not function words, takes the free word’s place in the real sentence, and blocks 1 to 3 give its point\.
BernBRSruns withN=400N=400and the defaults of Appendix[D](https://arxiv.org/html/2611.22083#A4), on CPU with 8 threads per job\.相似文章
BeFit:将复杂性从权重转移到伯恩斯坦激活函数,以实现资源受限的传感
BeFit 是一个端到端框架,将模型容量从权重转移到可学习的伯恩斯坦多项式激活函数,使资源受限的微控制器能够运行无需乘法运算的 CNN,同时准确率比 ReLU CNN 高出 2.75 个百分点,执行速度最高可达 MLPerf Tiny DS-CNN 参考模型的 5.9 倍。
Neuro-Bayesian-Symbolic Residual Attention Shallow Network: 面向网络安全风险评估的可解释深度学习
介绍 Neuro-Bayesian-Symbolic Residual Attention Shallow Network (NBS-RASN),一种用于开源生态系统中可解释网络安全风险评估的混合神经架构,使用80个可解释神经元分布在12层,并带有硬约束以保证可解释性。
Bern2Edge:通过伯恩斯坦多项式网络进行边缘部署的神经符号编译器
Bern2Edge是一种神经符号编译器,能将预训练神经网络转换为伯恩斯坦多项式表示,以在FPGA上实现高效且可解释的边缘部署,显著降低延迟和资源使用,同时保持准确性。
Sigma-Branch: 面向动态推理的分层单路径网络重构,减少活跃参数
Sigma-Branch 将预训练的稠密网络重构成一个层次化二叉树结构,包含共享主干、路由器和专用叶子节点。在 CIFAR-100、ImageNet-1K 和 ModelNet40 上,每次推理的活跃参数减少 58-60%,同时精度下降不超过基线精确率的 1.72 个百分点。
Neural Bayesian Sequential Routing
介绍了神经贝叶斯顺序路由(NBSR),这是一个将神经推理建模为有向无环图(DAG)上的顺序证据积累的框架,使用狄利克雷-分类共轭更新,实现了不确定性量化、早期退出和资源理性推理。