Quadratic Characterizations for Reachability Analysis of Neural Networks

arXiv:2605.20482 · cs.LG, cs.SY, eess.SY · Submitted 2026-05-19 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Quadratic Characterizations for Reachability Analysis of Neural Networks".

Tom: The gist The resulting verified quadratic constraints define a sound overapproximation of the scalar relations over the considered domains.

Jane: First, who's behind it and why it matters.

Title and authors: Tom: We just covered the title and authors, focusing on what "Quadratic Characterizations for Reachability Analysis of Neural Networks" means in plain terms, which is about using quadratic constraints to give a sound overapproximation of scalar relations.

Jane: To put that simply, they are taking a relation—say, the input-output behavior of a neural network—and they're trying to find quadratic inequalities that are guaranteed to be true for all points satisfying that relation within a certain area.

Lu: The paper proposes generating these candidate quadratic inequalities locally by solving convex quadratic programs using samples from the actual relation and some exterior sample points.

Meng: So, they use the data—the samples—to create initial guesses for these functions, which isn't a guarantee of global correctness yet.

Tom: Right. But then, the crucial part is verification: they check if those local guesses are actually correct everywhere by solving sum-of-squares feasibility problems on subsets derived from the relation's structure.

Jane: That whole process is about building a set of verified quadratic functions that are guaranteed to be non-negative over the domain we care about, which defines a sound overapproximation.

Lu: They show how this works for both exact semialgebraic descriptions and when dealing with nonpolynomial relations, by using relaxed polynomial descriptions for the verification step.

Tom: It’s a multi-step process: sample data to guess locally, then solve SOS problems to prove it globally. That's the core mechanism of "Quadratic Characterizations for Reachability Analysis of Neural Networks."

Jane: So, if we look at what this means for someone who only listens to the show, it means we’re getting a mathematically sound way to approximate how these networks will behave without being overly conservative.

Lu: It connects directly with existing analysis frameworks based on QCs and pointwise integral quadratic constraints for static nonlinearities and uncertainties.

Meng: It’s not just a new tool; it’s an extension of established methods, which makes it more immediately applicable in research settings where these tools are already in use.

Tom: That's the key point: compatibility with existing frameworks makes this new method practical for real-world safety analysis.

The paper's summary: Tom: Now we’re looking at the actual summary of "Quadratic Characterizations for Reachability Analysis of Neural Networks," and it lays out how they tackle the problem of conservative characterizations in nonlinear systems.

Jane: Basically, they are addressing the conservatism inherent in generic analytical characterizations when you're dealing with nonlinear functions, which is a big problem in AI safety analysis.

Lu: They develop this framework to construct verified quadratic characterizations of scalar relations specifically within the two-dimensional real plane.

Meng: The method involves generating candidate quadratic inequalities locally via convex quadratic programs using samples from the relation and exterior sample points.

Tom: Those candidates are then rigorously verified globally by solving SOS feasibility problems on subsets S(i) defined by non-negativity constraints derived from the relation's structure.

Jane: If those SOS problems are feasible for every subset, it means the candidate quadratic function is guaranteed to be non-negative over the entire restricted domain.

Lu: The resulting set of verified constraints, Qcert, then defines a sound overapproximation of the original scalar relation S D, meaning S D is contained within Nq.

Tom: So the summary boils down to: local guessing followed by global proof via sum-of-squares certificates to get a verified quadratic characterization.

Jane: That’s a lot of math, but the practical implication for us is that we have a concrete procedure for getting mathematically sound bounds on network behavior.

Lu: And they show how this works even when the relation isn't perfectly polynomial by using relaxed polynomial descriptions in the verification step.

Meng: It shows they’re flexible enough to handle various types of relations, which is important because neural network functions aren't always simple polynomials.

Tom: Exactly. They’ve made it robust enough for a wider variety of network behaviors than just the simplest polynomial ones.

The paper's improvements: Tom: Let’s talk about the specific improvements they suggest in "Quadratic Characterizations for Reachability Analysis of Neural Networks," which are about making this method better than what came before.

Jane: The main improvement is moving from just candidate generation to a fully verified process, where the verification step uses SOS feasibility problems on subsets S(i).

Lu: This verification step, solving for sigma(i) j,k, ensures that the candidate quadratic function q cand k(z) remains non-negative across every relevant subset.

Meng: This level of rigor is what allows them to define the set Nq, which is a sound overapproximation of the original relation S D.

Tom: And they also introduce methods for ReLU networks, specifically blockwise repeated-ReLU coupling, which uses a matrix structure involving diagonal variables and Q(i)one <ref:2605.20482#pg1>.

Jane: That specific coupling technique seems to be a targeted way to reduce conservatism by exploiting dependencies between neurons and using tighter local bounds.

Lu: They show how this coupling helps in tightening the neurons' pre- and post-activation bounds, which is crucial for accurate analysis of ReLU networks.

Tom: And they demonstrate tangible results on benchmarks like tanh neural-network controllers, where their overapproximations are approximately six point four percent tighter than those of NNV and about one point two percent tighter than alpha, beta-CROWN bounds.

Jane: Those percentage improvements are significant because they show that this method can actually yield better results than established methods on specific problems.

Conclusion: Tom: We're wrapping up our discussion on "Quadratic Characterizations for Reachability Analysis of Neural Networks" and summarizing what this paper means overall for the field.

Jane: This paper presents a framework where you build verified quadratic characterizations that are sound overapproximations, which can be embedded into existing QC-based semidefinite programs.

Lu: The core contribution is developing a method to construct these constraints from sampled data and then verifying them globally using SOS certificates for various relation types.

Meng: It offers practical utility by providing verifiable safety conditions and methods for local bound tightening that improve accuracy on complex architectures like ReLU networks.

Tom: So, we have a method that allows researchers to move toward tighter bounds by using verified quadratic characterizations to define sound overapproximations of scalar relations.

Jane: It’s about creating a system where the mathematical structure of the relation dictates the constraints, giving us much more reliable results than generic approximations.

Lu: The compatibility with existing analysis frameworks is what makes this framework useful for integrating it into current AI safety analysis toolchains.

Meng: And that iterative refinement process using polytope propagation for hidden layers shows a path toward achieving the tightest output bounds possible on benchmarks like ACAS Xu.

Tom: That’s the picture of "Quadratic Characterizations for Reachability Analysis of Neural Networks." It’s a framework built on rigorous quadratic math to improve how we analyze neural network behavior.

cs.LG, cs.SY, eess.SY

Submitted: 2026-05-19

Updated: 2026-10-09

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 83/100

The gist: The gist The resulting verified quadratic constraints define a sound overapproximation of the scalar relations over the considered domains.

Key concepts

Quadratic Constraints (QCs): These are mathematical inequalities involving quadratic functions that are used to model nonlinearities and uncertainties. The paper uses them to define a sound overapproximation of the actual scalar relations being studied, ensuring that the resulting constraints safely bound the true behavior.
Sum-of-Squares (SOS) Certificates: SOS certificates are mathematical tools used to rigorously verify if a quadratic inequality holds true over an entire region. If an SOS certificate exists, it proves that the candidate quadratic inequality is valid globally, not just at sampled points.
Reachability Analysis: This involves determining all possible states or outputs a system (like a neural network) can reach given certain inputs. The paper uses verified QCs to create sound overapproximations of these reachable sets, providing safer and tighter bounds for control and safety analysis.

Terminology

Verification — 43× in this paper · explained in 2 episodes
Pruning — 5× in this paper · explained in 4 episodes
Benchmark — 4× in this paper · explained in 2 episodes
Robustness — 3× in this paper · explained in 5 episodes
SMT solver — 3× in this paper · explained in 2 episodes
Activation Function — 2× in this paper · explained in 1 episode
Formal Methods — 2× in this paper · explained in 3 episodes
Chebyshev Polynomials — 1× in this paper · explained in 2 episodes
Closed-Loop System — 1× in this paper · explained in 4 episodes
Elias — 1× in this paper · explained in 2 episodes
Generalization — 1× in this paper · explained in 13 episodes
Hybrid System — 1× in this paper · explained in 2 episodes
Regularization — 1× in this paper · explained in 3 episodes
Reinforcement Learning — 1× in this paper · explained in 4 episodes
Semidefinite Program (SDP) — 1× in this paper · explained in 2 episodes

Summary

The gist The resulting verified quadratic constraints define a sound overapproximation of the scalar relations over the considered domains.

How it works

The framework develops a method for constructing verified quadratic characterizations of scalar relations in the two-dimensional real plane. Candidate quadratic inequalities are locally generated by solving convex quadratic programs using samples from the relation and exterior sample points. These candidate functions are then verified globally using sum-of-squares certificates over an exact semialgebraic description or, in the case of nonpolynomial relations, over relaxed polynomial descriptions.

Data-Driven Candidate Generation and SOS Verification

The proposed approach consists of two stages: candidate generation from sampled data and verification by solving SOS feasibility problems.

Local decomposition and sampling involves defining subdomains Uk and computing a candidate function qcandk(z) = ckϕ(z), ck ∈ R6, by solving a convex quadratic program. The optimization problem (3) enforces prescribed inequalities on finitely many samples and does not guarantee global validity.
SOS-based verification for piecewise-polynomial relations involves solving a feasibility problem on each subset S(i), where qcandk is verified by finding σ(i) such that qcandk(z) - mi∑j=1σ(i)j,k(z) g(i)j(z) ∈ Σ[z].
The scalar activation σ is said to satisfy the QCs defined by Qcert if, for every pair (h1, h2) satisfying h2 = σ(h1), [h1 h2 1]Q⎡⎢⎢⎢⎣h1h2 1⎥⎥⎥⎥⎦ ≥ 0 for all Q ∈ Qcert.

ReLU-Specific Tightening for Feedforward Neural Network Reachability Analysis

For ReLU networks, methods are introduced to reduce conservatism by exploiting dependencies between neurons and tighter local bounds.

Blockwise repeated-ReLU coupling involves imposing a repeated-ReLU QC defined by a matrix of the form M(i)rep = M(i)1 + (T(i))⊺Q(i)2 T(i), where Q(i)1 is a diagonal matrix variable.

Examples

The paper demonstrates the utility of the approach through several examples.

For hyperbolic tangent, data-driven candidates are successfully verified using the procedure for nonpolynomial relations.
For unit saturation, since it admits an exact semialgebraic description, candidate generation and verification are carried out directly on the exact graph.
In reachability analysis of a tanh neural-network controller, the reachable-set overapproximations obtained using 180 polytope facets are approximately 6.4% tighter than those of NNV and approximately 1.2% tighter than those of α, β-CROWN.
In ReLU reachability and verification on ACAS Xu, COMB-PP results in the smallest bounds on average among all methods considered.

The paper concludes by presenting a framework for constructing verified quadratic characterizations of scalar static relations on bounded domains that are compatible with existing QC- and pointwise-IQCbased analysis methods.

REFERENCE RULES

Copy a token exactly as it is printed for you.

Improvements for AI systems

Improve reachability analysis for neural networks by employing verified quadratic characterizations to define a sound overapproximation of the scalar relations over the considered domains. This allows for generating domain-dependent quadratic characterizations that constitute an alternative to generic sector- or slope-based descriptions specifically for smooth activations like tanh, leading to tighter bounds than generic methods.
Reduce conservatism in QC-based reachability analysis for ReLU networks by exploiting dependencies between neurons and tighter local bounds, which involves combining the exact quadratic characterization [4] with blockwise coupling of repeated ReLU units [10] and tightening of the neurons’ pre- and post-activation bounds. This results in an SDP formulation that is more accurate than treating activations as independent units.
Enhance the robustness of neural network safety verification by incorporating verified quadratic characterizations derived in Section III into QC-based semidefinite programs, such as those found in [4]. This allows for the computation of a polytopic overapproximation for the output reachable set by solving optimization problems like (7) or (8), leading to verifiable safety conditions.
Develop tighter bounds on hidden layer activations by implementing local bound tightening using polytope propagation across hidden layers, which involves computing a postactivation polytope and solving linear programs to find improved bounds. This procedure is repeated sequentially, yielding the tightest output bounds for reachability analysis, as demonstrated in the ACAS Xu benchmark.
Implement neuron pruning based on exact scalar constraints where ReLU units are known to be inactive or active; if φli ≤ 0, then neuron i is always inactive and ϑli = 0, the neuron can be removed from the analysis, thus improving computational efficiency while maintaining accuracy.

Sources

Adversarial Reinforcement Learning for Robust Control of Fixed-Wing Aircraft under Model Uncertainty