Teaching Machines to Doubt Themselves: A New Framework That Makes AI Safety Certificates Tighter

Imagine you are certifying that a drone controlled by a neural network will never hit an obstacle, no matter how its sensors flutter within their known error margins. You do not need to know the exact output of the network for every possible input — that would require solving an astronomically large search problem. You need something simpler and more powerful: a guaranteed upper bound on the worst the network could do. Get that bound tight enough, and you can sign off on the system. Leave it too loose, and you either reject a perfectly safe drone or, worse, accept a dangerous one under a false certificate.

This is the central problem of neural network reachability analysis: computing or bounding the set of outputs a network can produce over a given range of inputs. It sits at the foundation of AI safety for autonomous vehicles, medical diagnostics, and any other domain where a learning-enabled system must be certified before deployment. And it is, in general, computationally intractable to solve exactly — which is why the field has spent years building tractable overapproximations, bounds that are always safe (they never underestimate the danger) but are often far more conservative than they need to be.

A new framework called HiTaB (Hierarchical End-to-End Taylor Bounds), developed by Taha Entesari and Mahyar Fazlyab at Johns Hopkins University, takes a significant step toward closing that gap. The key insight: existing state-of-the-art methods for smooth networks exploit at most the network's second derivative — its curvature — but stop there. HiTaB goes one order higher, bounding how quickly that curvature itself changes. The result is a hierarchy of safety certificates that are provably tighter than anything currently available for smooth, differentiable neural networks (Entesari & Fazlyab, 2026).

The Science

The problem HiTaB addresses can be stated precisely. Given a neural network representing a function $f:{\mathbb{R}}^n\to \mathbb{R}$ and a ball of admissible inputs $\mathcal{B}(x_c,\epsilon )$ — all inputs within distance $\epsilon$ of some nominal point $x_c$ — what is the largest output $f$ can produce? Formally:

$$\underset{x\in \mathcal{B}(x_c,\epsilon )}{\max }f(x)$$

Solving this exactly is nonconvex and NP-hard in general. The practical alternative is to find a majorizer $\bar{f}$: a function that is always at least as large as $f$, but whose maximum over the input ball can be computed cheaply. The tighter $\bar{f}$ is to $f$, the more useful the resulting certificate.

Prior work has built these majorizers from Taylor expansions — the mathematical technique of approximating a function near a point using its value, slope, and curvature. A zeroth-order bound uses only the function value and a global Lipschitz constant (a measure of how fast the output can change at all). A first-order bound adds the local gradient. A second-order bound adds the Hessian — the matrix of second derivatives that captures local curvature. Each step tightens the approximation, but each also requires computing something harder about the network.

The bottleneck HiTaB solves is the third step. A second-order Taylor approximation of $f$ comes with a remainder term — the error between the approximation and reality — that scales with how quickly the Hessian itself changes. That rate of change is formalized as $L_{{\nabla }^{2}f}$, the Lipschitz constant of the Hessian (informally: the maximum rate at which the network's curvature can shift as inputs move). If you can bound $L_{{\nabla }^{2}f}$, you can certify that the remainder of your Taylor approximation never exceeds $\frac{1}{6}{L}_{{\nabla }^{2}f}\Vert \delta {\Vert }_2^3$, where $\delta$ is the size of the perturbation. That cubic scaling is the key: for small perturbations — precisely the regime that matters most in robustness certification — a cubic error term is much smaller than the quadratic error terms of first-order methods.

No previous tool had computed $L_{{\nabla }^{2}f}$ efficiently for deep networks. HiTaB provides the first practical algorithm to do so.

The work is grounded in a clean mathematical hierarchy. Three majorizers are derived, each indexed by the highest order of derivative information used:

• ${\bar{f}}_0$: uses only the function value and global Lipschitz constant $L_f$
• ${\bar{f}}_1$: adds the local gradient $\nabla f(x_c)$ and gradient Lipschitz constant $L_{\nabla f}$
• ${\bar{f}}_2$: adds the local Hessian ${\nabla }^{2}f(x_c)$ and Hessian Lipschitz constant $L_{{\nabla }^{2}f}$

The second-order majorizer takes the form:

$${\bar{f}}_2(x_c,\delta )=f(x_c)+\nabla f(x_c{)}^{\top }\delta +\frac{1}{2}{\delta }^{\top }{\nabla }^{2}f(x_c)\delta +\frac{1}{6}{L}_{{\nabla }^{2}f}\Vert \delta {\Vert }_2^3$$

The last term is the certified cubic remainder — the mathematical guarantee that the Taylor approximation never understates the true maximum by more than this amount. Because all three bounds can be computed once the required Lipschitz constants are in hand, the framework automatically selects the minimum of the three certificates at runtime, ensuring the tightest possible guarantee in every case.

What They Found

Hierarchy of Taylor Bound Orders: Remainder Scaling

Label	Value
Zeroth-order (linear)	1 relative remainder at ε=1
First-order (quadratic)	0.5 relative remainder at ε=1
Second-order (cubic)	0.167 relative remainder at ε=1

Remainder terms from Section 3 of Entesari & Fazlyab (2026). Assumes equal Lipschitz constants for comparison. At smaller ε, the cubic second-order term shrinks far faster than lower-order terms.

The central theoretical result is a precise condition under which each higher-order bound beats the one below it. The second-order certificate ${\bar{f}}_2^{\text{sb}}$ is provably tighter than the first-order certificate ${\bar{f}}_1^{\ast }$ whenever:

$$\epsilon \le \frac{3}{L_{{\nabla }^{2}f}}\left(L_{\nabla f}-{\left({\lambda }_{\max }({\nabla }^{2}f(x_c))\right)}_{+}\right)$$

Here ${\lambda }_{\max }({\nabla }^{2}f(x_c))$ is the largest eigenvalue of the Hessian at $x_c$ — a measure of the strongest local upward curvature — and $(a{)}_{+}=\max (a,0)$. The threshold is always nonnegative, because $L_{\nabla f}\ge {\sup }_x{\lambda }_{\max }({\nabla }^{2}f(x))$ by definition. This means the second-order bound never hurts: there always exists a range of perturbation sizes for which it wins, and when it doesn't, the framework falls back automatically to the first-order result (Entesari & Fazlyab, 2026).

An analogous condition characterizes when the first-order bound beats the zeroth-order bound:

$$\epsilon \le \frac{2(L_f-\Vert \nabla f(x_c){\Vert }_2)}{L_{\nabla f}}$$

The improvement is greatest when the local gradient is small relative to the global Lipschitz constant — when the function is flatter locally than it is globally. This is exactly what happens at saddle points, near local optima, or in well-trained networks where most inputs land in stable regions of the output space.

Remainder Advantage of Second-Order Bound at Small Perturbations

Label	Value
ε = 1.0	3 ratio
ε = 0.5	6 ratio
ε = 0.25	12 ratio
ε = 0.1	30 ratio
ε = 0.01	300 ratio

Computed from remainder formulas in Section 3: first-order remainder = ½L∇f ε², second-order = ⅙L∇²f ε³. Ratio = 3/ε (assuming equal Lipschitz constants). Demonstrates the cubic advantage of HiTaB in the small-perturbation regime relevant to branch-and-bound subdivision.

The technical core of the paper is a layerwise compositional algorithm for bounding $L_{{\nabla }^{2}f}$ in feedforward networks. For a network with layers indexed $1$ through $L$, the algorithm propagates curvature bounds forward through each layer. At layer $I$, the Hessian Lipschitz constant of the $j$-th output neuron satisfies the bound:

$$L_{{\nabla }^2{a}_j^I}\le L_{{\nabla }^2{F}_j^I}{L}_{a^{I-1}}^3+2L_{D{a}^{I-1}}{L}_{a^{I-1}}{L}_{\nabla F_j^I}+\sum _{i=1}^{N_{I-1}}\left(L_{{\partial }_i{F}_j^I}{L}_{a^{I-1}}{L}_{D{a}_i^{I-1}}+L_{{\nabla }^2{a}_i^{I-1}}\underset{x}{\sup }|{\partial }_i{F}_j^I(x)|\right)$$

Each quantity in this expression has a concrete meaning: $L_{a^{I-1}}$ is the Lipschitz constant of the previous layer's output (its maximum rate of change), $L_{D{a}^{I-1}}$ is the Lipschitz constant of its Jacobian (how fast the layer's slope changes), and $L_{{\nabla }^2{F}_j^I}$ depends only on the activation function and the weights of the current layer. All of these can be computed with existing certified tools — the new contribution is the composition rule that chains them into a network-level bound on $L_{{\nabla }^{2}f}$.

For smooth activations like sigmoid or tanh, the algorithm exploits the fact that ${\sigma }^{\prime \prime }$ (the second derivative of the activation) is itself Lipschitz with constant $L_{{\sigma }^{\prime \prime }}$. The bound on $L_{{\nabla }^2{F}_j^I}$ then becomes simply $L_{{\sigma }^{\prime \prime }}\Vert W_{j,:}^I{\Vert }_2^3$ — a product of the activation's smoothness and the cube of the weight row's norm. Crucially, these are quantities engineers already know for any trained network.

The framework applies to both \ell_2$-bounded perturbations (Euclidean balls, relevant for adversarial robustness) and $\ell_\infty$-bounded perturbations (box constraints, which are the standard model in image classifier certification). For $\ell_\infty inputs, the bounds are reformulated using norm equivalences and matrix operator norms, preserving the same hierarchical structure.

Why This Changes Things

To see why this matters in practice, consider the quadrotor control problem demonstrated in the paper. A drone navigating through space is governed by nonlinear dynamics, and a neural network controller produces thrust commands from sensor readings. Certifying that the drone will not enter a collision zone requires bounding the reachable set of the closed-loop system — essentially answering the reachability question repeatedly, at each time step, for each possible state. Even a small tightening of the per-step bound compounds across time horizons: a looser bound at step one inflates the reachable set fed into step two, and so on. The drone's "certified safe zone" shrinks with every conservative approximation that compounds through the trajectory.

HiTaB's tighter per-step certificates directly translate to less conservative reachable sets over the full horizon. The paper demonstrates the framework on a quadrotor navigating around two spherical obstacles, computing trajectory reachable sets with a tolerance of $0.001$ (Entesari & Fazlyab, 2026). The key advantage is that the second-order bound's cubic remainder $\frac{1}{6}{L}_{{\nabla }^{2}f}{\epsilon }^3$ shrinks much faster than the quadratic remainders of first-order methods as $\epsilon$ decreases — and in branch-and-bound verification, where the input domain is recursively subdivided into smaller and smaller subregions, this faster decay is exactly what accelerates convergence.

The broader significance is that smooth networks — networks using sigmoid, tanh, SiLU, GELU, or other differentiable activations — are increasingly common in safety-critical applications. GELU activations dominate modern transformers; smooth activations are preferred in physics-informed networks and neural ordinary differential equations. Yet the verification literature has focused overwhelmingly on ReLU networks, which are piecewise linear and admit mixed-integer linear programming formulations. HiTaB opens a principled route to tighter verification for the smooth network architectures that real systems increasingly rely on.

The framework also has a structural elegance that matters for trust. The hierarchy is not a heuristic — it comes with provable monotonicity conditions that tell practitioners exactly when each higher-order bound will win. This is not "try the second-order method and see"; it is "the second-order method is guaranteed to be better whenever $\epsilon$ is smaller than this computable threshold." That kind of explicitness is rare and valuable in safety engineering, where a practitioner needs to justify every design choice.

Information Exploited by Each Verification Tier

Label	Value
Function value f(xc)	1
Global Lipschitz Lf	1
Local gradient ∇f	0
Gradient Lipschitz L∇f	0
Hessian ∇²f	0
Hessian Lipschitz L∇²f	0

Based on Section 3 of Entesari & Fazlyab (2026). Second-order bound (HiTaB) additionally uses the Hessian ∇²f(xc) and the Hessian Lipschitz constant L∇²f — quantities no prior reachability framework for smooth networks had bounded efficiently.

What's Next

The most immediate extension flagged by the researchers is integration into complete branch-and-bound verification pipelines. Modern verifiers like $\alpha$-CROWN and BaB-based frameworks subdivide the input space recursively, solving a reachability problem at each node. HiTaB's bounds slot naturally into this paradigm: tighter bounds at each node mean the verifier can prune branches faster, reducing the total computation needed to certify or refute a property. The paper demonstrates the conceptual integration but leaves full-scale empirical comparison to future work.

There are real caveats. The layerwise bound on $L_{{\nabla }^{2}f}$ is an overapproximation — it is guaranteed never to underestimate the true Hessian Lipschitz constant, but it may overestimate it, especially in deep networks where multiplicative compounding across layers introduces conservatism. This is the same fundamental tension that afflicts all propagation-based Lipschitz estimates: the bound is provably safe, but it may be loose. Future work could sharpen the layer-level estimates using semidefinite programming relaxations (analogous to LipSDP for first-order constants) or by exploiting correlations between layers that the current elementwise bounds ignore.

The framework currently handles scalar-valued outputs — a single neuron or a single logit. Extensions to vector-valued networks, relevant for multi-output controllers or multi-class classifiers, would require bounding the Hessian Lipschitz constant of the full Jacobian, a technically richer problem. The paper notes this as an open direction.

There is also an interesting theoretical question lurking here: the hierarchy stops at second-order information, but the same compositional logic could in principle be extended to third-order bounds, using the Lipschitz constant of the third derivative to control a quartic remainder. Whether the additional complexity pays off — whether networks in practice have third derivatives that are meaningfully bounded by computable quantities — is an open empirical and theoretical question.

What HiTaB establishes, for the first time, is that the mathematics of neural network verification does not have to stop at curvature. The compositional structure of deep networks, which makes them hard to analyze globally, is also what makes them amenable to hierarchical smoothness analysis — each layer's contribution to higher-order behavior can be bounded independently and composed. That insight, once formalized, turns a seemingly intractable object (the Hessian Lipschitz constant of a 50-layer network) into something computable in a forward pass.

The dream of certifiably safe AI — not just probably safe, not just empirically robust, but provably safe in the mathematical sense — is still distant for large-scale systems. But it is built from exactly these kinds of incremental, principled advances: tighter bounds, sharper conditions, cleaner hierarchies. HiTaB adds a new rung to that ladder, and in safety-critical engineering, every rung counts.