🤖 machine learning

The Complexity of Verifying Feedforward Neural Networks in Quantised Settings

This paper establishes the computational complexity landscape for verifying feedforward neural networks in quantised settings, demonstrating that verification remains NP-complete for networks with fixed arithmetic precision under both linear and bit-vector specifications, while providing new upper bounds for dynamically quantised networks under bit-vector specifications.

Original authors: Eric Alsmann, Martin Lange, Marco Sälzer

Published 2026-05-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Eric Alsmann, Martin Lange, Marco Sälzer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart robot (a Feedforward Neural Network) that makes decisions, like recognizing a cat in a photo or steering a self-driving car. Before we let this robot loose in the real world, we need to be 100% sure it won't make a dangerous mistake. This process is called verification.

For a long time, scientists tried to verify these robots by pretending they were made of perfect, infinite-precision math (like using a ruler that can measure down to the size of an atom, forever). But in the real world, computers aren't perfect. They use quantized arithmetic, which is like using a ruler that only has marks every millimeter. You have to round things off, and sometimes you run out of space (overflow).

This paper asks a big question: Does switching from "perfect math" to "real-world, rounded math" make it much harder to prove the robot is safe?

Here is the breakdown of their findings, using some everyday analogies:

1. The Three Types of Robots

The authors looked at three different ways these robots are built:

The Ideal Robot (Rational FNN): Built with perfect, infinite-precision math.
The Pre-Quantized Robot (Quantised FNN): Built from the start using the "millimeter ruler" (finite-width math).
The Converted Robot (Dynamically Quantised): A perfect robot that we force to use the "millimeter ruler" after it was already trained.

2. The Two Types of Safety Rules

To check if the robot is safe, we give it rules. The paper looks at two kinds of rulebooks:

The Linear Rules (LP): These are simple, straight-line rules. Think of them like a traffic sign saying, "If speed is under 50, you are safe." These rules are easy to visualize as a smooth, convex shape.
The Bit-Vector Rules (BV): These are complex, "bit-level" rules. Think of them like a security system that checks specific switches inside the computer's brain. "If bit 3 is on AND bit 7 is off, but bit 2 is on, then it's a problem." These can describe very jagged, complex, non-linear shapes.

3. The Main Findings: Is it Harder?

Scenario A: Simple Rules (Linear Constraints)

The Result: No, it's not harder.
Whether the robot is perfect or uses the "millimeter ruler," and whether the rules are simple or complex, checking safety remains NP-complete.

The Analogy: Imagine trying to find a specific key in a giant, messy drawer. Whether the keys are made of gold (perfect math) or plastic (rounded math), and whether the drawer is organized or chaotic, the difficulty of finding the key doesn't change. It's still a "hard" problem, but it's the same level of hard as before.
Why this matters: It means we don't need to invent entirely new, super-powerful computers to verify real-world robots. The tools we already have for perfect math can be adapted for real-world math without getting exponentially slower.

Scenario B: Complex Rules (Bit-Vector Constraints)

The Result: It depends on the robot's "brain" size.

If the robot is already built with the "millimeter ruler": Checking safety is still NP-complete (same difficulty as before).
If we take a perfect robot and force it to use the "millimeter ruler" (Dynamic Quantisation): This gets much harder. It jumps to PSPACE-complete.
- The Analogy: Imagine you have a perfect recipe (the perfect robot). Now, you have to cook it in a tiny kitchen with a specific, limited set of pots and pans (the finite-width arithmetic). If you just use the limited pots from the start, it's fine. But if you try to translate the perfect recipe into the limited kitchen while cooking, the number of possible ways things can go wrong explodes. You have to keep track of so many "what-if" scenarios (like aligning numbers that are different sizes) that the memory required to check them all grows massively.

4. The Floating-Point Mystery

The paper also looked at floating-point numbers (the standard way computers handle decimals, like 3.14).

Fixed Exponent: If the range of numbers is fixed (like a ruler with a fixed max length), the difficulty stays manageable (PSPACE).
General Floating-Point: If the range can change wildly, the difficulty might jump even higher (NEXPTIME).
The Analogy: In floating-point math, numbers can be very small or very large. To add them, the computer has to "align" them first (like lining up decimal points). If the numbers are wildly different sizes, the computer has to buffer a huge amount of data to do this alignment. The authors found that this "alignment" step is what makes the problem potentially much, much harder to solve.

Summary

The paper essentially says:

Good News: For the most common type of safety check (linear rules), switching to real-world, rounded math doesn't make the job impossible. It's still the same level of difficulty as the theoretical perfect math.
Bad News: If you are using very complex, bit-level rules on a perfect robot that you are forcing to use rounded math, the job becomes significantly harder (PSPACE).
The Unknown: If you use standard floating-point math with wild ranges, the job might be even harder, but the authors aren't 100% sure yet; they just know it's at least as hard as the "PSPACE" level.

In short: Quantization (rounding) doesn't break verification for simple rules, but it does make complex, dynamic scenarios much more computationally expensive.

Technical Summary: The Complexity of Verifying Feedforward Neural Networks in Quantised Settings

Problem Statement

The paper investigates the computational complexity of formally verifying Feedforward Neural Networks (FNNs) under quantised settings. While the reachability problem for FNNs operating over real-valued arithmetic (rational weights) is established as NP-complete, practical implementations rely on finite-width arithmetic (e.g., 64-bit floating-point or fixed-point numbers). This shift introduces quantisation effects such as rounding, overflow, and underflow.

The authors address a potential gap in understanding: does the move from idealised real-valued arithmetic to discrete, finite-width arithmetic increase the computational complexity of verification? Furthermore, they examine how the complexity changes based on:

Specification Formalisms: Linear Programming (LP) constraints versus Bit-Vector (BV) logics (which allow non-linear, bit-level reasoning).
Network Definition: Whether the FNN is defined with exact rational weights (Rational FNN) or pre-quantised weights (Quantised FNN).
Parameter Encoding: Whether the bit-width of the arithmetic is given as part of the input in unary (realistic for hardware register sizes) or binary (realistic for decimal specifications).

Methodology

The authors formalise five distinct reachability decision problems, denoted as REACH, varying by the arithmetic type and specification language:

REACHQ(LP): Rational FNNs with LP specifications (standard setting).
REACHF(LP): Quantised FNNs (weights already in finite-width arithmetic) with LP specifications.
REACHF(BV): Quantised FNNs with Bit-Vector specifications.
REACH(F, LP): Rational FNNs where the target finite-width arithmetic $F$ is part of the input (dynamic quantisation) with LP specifications.
REACH(F, BV): Rational FNNs with dynamic quantisation and Bit-Vector specifications.

Analytical Approach:

Complexity Lower Bounds: The authors utilize reductions from known hard problems (e.g., 3SAT) to establish NP-hardness and PSPACE-hardness. They demonstrate that standard "gadgets" used to encode Boolean logic into FNNs (using ReLU activations) remain valid even under finite-width arithmetic, provided the arithmetic can represent small integers and fractions like $1/2$ .
Complexity Upper Bounds:
- For LP specifications, the authors rely on the polynomial bound of solution sizes in linear programming (Theorem 1) to show that a witness (input vector) can be guessed and verified in polynomial time.
- For BV specifications with dynamic quantisation, the authors employ Succinct Non-deterministic Finite Automata (NFA). They construct automata that represent the input-output relation of the quantised FNN and the specification formulas. The state space of these automata is exponentially large but described compactly (succinctly).
- They distinguish between fixed-point and floating-point arithmetic. For floating-point, they note that general arithmetic requires alignment shifts that depend on the exponent difference. If the exponent width is unbounded (given in binary), the alignment buffer size becomes exponential, potentially breaking PSPACE bounds. They restrict their PSPACE upper bound proofs to cases where the exponent width is constant.

Key Contributions and Results

The paper establishes a comprehensive complexity landscape, summarised in Table 1 of the text:

1. Linear Programming (LP) Specifications

REACHQ(LP): Reaffirmed as NP-complete (citing Sälzer and Lange, 2021).
REACHF(LP): Proven NP-complete. The authors show that even with pre-quantised weights, the problem remains in NP because the input size of the witness is polynomial relative to the network size.
REACH(F, LP): Proven NP-complete. Even when the bit-width parameters are part of the input (dynamic quantisation), the problem remains NP-complete. The authors argue that the size of the witness remains polynomially bounded relative to the input size, regardless of whether bit-widths are encoded in unary or binary.

2. Bit-Vector (BV) Specifications

REACHF(BV): Proven NP-complete. For networks already quantised, the use of bit-vector logic does not increase complexity beyond NP.
REACH(F, BV) (Fixed-point & Floating-point with constant exponent width): Proven PSPACE-complete.
- Lower Bound: Matches the PSPACE-hardness result previously established by Henzinger et al. (2021).
- Upper Bound: The authors provide the first matching PSPACE upper bound. They achieve this by reducing the problem to the non-emptiness problem of succinctly represented NFAs.
REACH(F, BV) (General Floating-point): The problem is PSPACE-hard and lies within NEXPTIME.
- The authors note that for general floating-point arithmetic (where exponent width is variable and given in binary), the alignment step in addition/multiplication requires a buffer size that depends on the exponent difference. This prevents the construction of a succinct NFA with polynomial description size, leaving the exact upper bound open (currently NEXPTIME).

Significance and Claims

The paper claims to resolve a "widespread misunderstanding" regarding the complexity of quantised FNN verification, specifically addressing the results of Henzinger et al. (2021).

Clarification of Complexity Drivers: The authors argue that the jump from NP to PSPACE observed in previous work is not caused by quantisation itself, but by the combination of dynamic quantisation (where the arithmetic is part of the input) and the use of Bit-Vector specifications. For standard linear specifications, quantisation does not increase the complexity class; it remains NP-complete.
Feasibility of Tools: The results suggest that developing sound verification tools for quantised FNNs using linear specifications is feasible without asymptotic overhead compared to existing real-valued solvers, as both remain NP-complete.
Upper Bounds for BV: The paper complements the known PSPACE-hardness of dynamic quantised verification with BV specifications by establishing PSPACE-completeness for fixed-point and bounded-exponent floating-point arithmetic.
Open Problems: The authors modestly identify that for general floating-point arithmetic with unbounded exponents, the alignment requirement may push the problem beyond PSPACE (into NEXPTIME), and it remains an open question whether a matching lower bound can be proven.

In conclusion, the paper provides a rigorous classification showing that while bit-vector specifications on dynamically quantised networks introduce PSPACE complexity, the standard case of linear constraints on quantised networks retains the NP-completeness of the rational case.