The Complexity of Verifying Feedforward Neural Networks in Quantised Settings

Eric Alsmann, Martin Lange, Marco Sälzer · 2026

Read The Complexity of Verifying Feedforward Neural Networks in Quantised Settings by Eric Alsmann, Martin Lange, Marco Sälzer (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-29537.txt.

Introduction

Eric Alsmann, Martin Lange, and Marco Sälzer map how hard it is to verify feedforward neural networks with quantized weights. They split exact-weight rational networks, quantized networks with finite-width math, and dynamic quantized networks run under given math. Two styles are used: linear programming constraints and bit-vector logic, which can express nonlinear constraints. With fixed width, checking stays NP-complete under both styles, matching the rational case. For dynamic quantization with bit-vector rules, upper bounds add to known PSPACE-hardness.

Catalog record

CREATOREric Alsmann, Martin Lange, Marco Sälzer
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE49047
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.29537

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Complexity of Verifying Feedforward Neural Networks in Quantised Settings Eric Alsmann, Martin Lange, Marco Sälzer Abstract We investigate the computational complexity of neural network verification in quantised settings. We distinguish three classes of Feedforward Neural Networks (FNNs): rational FNNs with exact rational weights, quantised FNNs whose weights come from a finite-width arithmetic, and dynamically quantised FNNs in which rational networks are evaluated with respect to a given finite-width arithmetic. We consider two types of specifications used in the literature. Linear programming (LP) specifications are conjunctions of linear constraints, while bit-vector (BV) specifications allow reasoning at the bit level and can express non-linear constraints. Our results give a complexity landscape of these verification problems. For quantised FNNs with fixed arithmetic precision, we show that verification under both LP and BV specifications remains NP-complete, matching the complexity of the rational case. For dynamically quantised FNNs with BV specifications, we establish upper bounds, complementing a previously known PSPACE-hardness result. 1 Introduction Feedforward Neural Networks (FNN) are ubiquitous in deep learning, not only as a stand-alone model for classifying inputs or transforming input values into outputs, but also as components in other machine learning models, for instance transformers, cf. 17 . The ever-growing quest for machine-learning methods to solve various computational tasks, in particular for safety-critical applications, comes with a need for methods that formally verify properties like safety or robustness of such models, including FNN. In this paper, we are concerned with verification tasks of the following form: given an FNN N and a safety property \varphi , decide whether \varphi holds for N or not. To distinguish this from other forms of verification, such as testing N on a sample set of inputs or adjusting the training procedure to meet certain safety criteria, we refer to this as static (FNN) verification . In its most rigorous form, static verification tasks are stated as formal decision problems. In one of the most prominent variants, addressed by a wide-range of practical solvers, cf. 1 ; 2 , or analysed formally, cf. 16 ; 19 ; 6 , static verification is concerned with the question of whether the pairs of inputs and corresponding outputs of a given FNN satisfy certain linear constraints. Problems of this kind are often referred to as reachability problems, cf. 7 , and other formal problems like robustness can usually be reduced to reachability. The reachability problem for FNN was claimed (see 9 ; 10 ; 13 ) and shown (see 15 ; 16 ) to be NP -complete. In this setting, FNN are considered to be mappings on real-valued vector spaces. In practice, the arithmetic operations internal to the FNN are of course executed not in arithmetic over \mathbb{R} which would be infeasible on any bounded-memory computer, but in some fixed-width arithmetic using 64bit floating-point or fixed-point numbers for instance. This shift from real-valued inputs and outputs to such discrete values is also known as quantisation , and it comes not only with a loss of precision but also with artefacts like rounding or over-/underflows. One may therefore argue that ( i ) NP -completeness of the reachability problem for FNN in arithmetic over \mathbb{R} does not necessarily predict the computational complexity of formal verification for FNN over a quantised arithmetic, and ( ii ) that the quantised setting is more interesting for practical purposes anyway. We investigate the computational complexity of formal verification, i.e. reachability, for quantised FNN. Quantisation does not make formal verification easier, i.e. NP -hardness remains a lower bound. This is not really surprising since computational hardness is often tightly linked to discretisation, see for instance the NP -completeness of Mixed-Integer Linear Programming versus the polynomial-time solvability of \mathbb{R} -valued linear programs. 6 recently studied the verification problem for quantised FNN and provided a result that suggests higher complexity, namely PSpace instead of NP . There seems to be some widespread misunderstanding about the actual results, perhaps fuelled by the fact that the paper is seen to be hard to read. First of all, 6 only provides a lower bound of PSpace -hardness, not PSpace -completeness. Second, they consider a richer specification language for safety properties: while NP -completeness holds for safety properties that are convex sets of vectors, i.e. specifications in the form of linear programs, 6 uses bit-vector logics which allow non-convex sets to be specified. Thus, the increase in complexity from NP to PSpace is not due to quantisation, as that paper may suggest, but due to the use of a richer specification language for safety properties. In this paper, we aim to provide an overall picture of the computational complexity of formal verification for quantised FNN. We classify the complexities depending on ( i ) the involved specification formalisms for safety properties, as they are commonly used in the literature, ( ii ) the exact nature of the fixed bit-width arithmetic that determines how the FNN’s internal computations are performed on common hardware architectures and, finally, ( iii ) the dependence on the parameter determining the bit-width of such numbers, in particular whether this is given in unary or in binary. The motivation for studying the effect that this parameter has, also comes from practice: suppose we import a trained FNN to run on our hardware. The FNN may come with advice saying that arithmetic operations should be carried out with a certain bit-width. In this case, that width would normally be given as a decimal number, i.e. the actual width is exponential in the representation size of that parameter. On the other hand, when verifying a quantised FNN on the hardware where it already resides, the bit-width rather corresponds to the size of actual CPU registers, and therefore a unary encoding of this length may be a more realistic measure of the space needed to represent such quantised values. The paper is organised as follows. In Section 2 , we provide thorough definitions of all fundamentals necessary for the findings presented in this paper. In Section 3 , we formally present reachability problems of FNN as decision problems. In Section 4 , we examine the complexity of reachability in different quantisation settings where specifications are given by linear constraints. In Section 5 , we study the complexity of verifying quantised FNN in the context of bit-vector logic, complementing the work of 6 . Finally, in Section 6 , we briefly discuss our findings and outline prospective next steps. 2 Preliminaries Numbers, vectors and matrices. We exclusively consider numbers from \mathbb{Q} . Typically, we denote vectors using small, bold symbols like \bm{x} , \bm{y} or \bm{z} and matrices using big, bold symbols like \bm{A} , \bm{B} or \bm{C} . We denote by \bm{x}_{i} the i -th entry of vector \bm{x} and by \bm{A}_{i,j} the entry in the i -th row and j -th column of matrix \bm{A} . Let x\in\mathbb{Q} with p\in\mathbb{Z} and q\in\mathbb{N}^{>0} such that x=\frac{p}{q} . If not stated otherwise, we define the size of x , denoted by |x| , as |x|=|p|+|q| where |p|=(\lfloor\log_{2}(p)+1\rfloor)+1 and |q|=\lfloor\log_{2}(q)+1\rfloor . Analogously, we extend the definition of |\cdot| to vectors \bm{x}\in\mathbb{Q}^{m} and matrices \bm{A}\in\mathbb{Q}^{m\times n} by |\bm{x}|=\sum_{i=1}^{m}|\bm{x}_{i}| and |\bm{A}|=\sum_{i=1}^{m}\sum_{j=1}^{n}|\bm{A}_{i,j}| . Finite-width arithmetics. We consider two kinds of finite arithmetics: fixed- and floating-point

Read the complete text