The Complexity of Verifying Feedforward Neural Networks in Quantised Settings

• URL: http://arxiv.org/abs/2605.29537v1
• Date: Thu, 28 May 2026 07:52:29 GMT
• Title: The Complexity of Verifying Feedforward Neural Networks in Quantised Settings
• Abstract summary: We investigate the computational complexity of neural network verification in quantised settings.<n>For quantised FNNs with fixed arithmetic precision, we show that verification under both LP and BV specifications remains NP-complete.<n>For dynamically quantised FNNs with BV specifications, we establish upper bounds, complementing a previously known PSPACE-hardness result.
• Score: 7.742297876120561
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Generalization Bounds of Spiking Neural Networks via Rademacher Complexity [58.338455812259724]
  Spiking Neural Networks (SNNs) have garnered increasing attention as one of bio-inspired models due to their great potential in neuromorphic computing and computation.<n>Recent advances disclosed an excitation-dependent and architecture-related generalization bound such that the Rademacher complexity of SNNs with firing can be upper bounded by an exponential function.<n>We theoretically investigate the generalization bounds of SNNs with several integration-and-fire schemes via Rademacher complexity.
  arXiv  Detail & Related papers  (2026-04-26T14:24:48Z)
• On Integer Programming for the Binarized Neural Network Verification Problem [3.342097413151171]
  Binarized neural networks (BNNs) are feedforward neural networks with binary weights and activation functions.<n> verification problem seeks to determine whether a small perturbation of a given input can lead it to be misclassified by the BNN.
  arXiv  Detail & Related papers  (2025-10-01T23:43:18Z)
• On the Hardness of Training Deep Neural Networks Discretely [0.0]
  We show that the hardness of neural network training (NNT) is dramatically affected by the network depth.<n>Specifically, we show that, under standard assumptions, D-NNT is not in the class NP even for instances with fixed dimensions and dataset size.<n>We complement these results with a comprehensive list of NP-hardness lower bounds for D-NNT on two-layer networks.
  arXiv  Detail & Related papers  (2024-12-17T16:20:29Z)
• An Automata-Theoretic Approach to Synthesizing Binarized Neural Networks [13.271286153792058]
  Quantized neural networks (QNNs) have been developed, with binarized neural networks (BNNs) restricted to binary values as a special case. This paper presents an automata-theoretic approach to synthesizing BNNs that meet designated properties.
  arXiv  Detail & Related papers  (2023-07-29T06:27:28Z)
• Benign Overfitting in Deep Neural Networks under Lazy Training [72.28294823115502]
  We show that when the data distribution is well-separated, DNNs can achieve Bayes-optimal test error for classification. Our results indicate that interpolating with smoother functions leads to better generalization.
  arXiv  Detail & Related papers  (2023-05-30T19:37:44Z)
• Power and limitations of single-qubit native quantum neural networks [5.526775342940154]
  Quantum neural networks (QNNs) have emerged as a leading strategy to establish applications in machine learning, chemistry, and optimization. We formulate a theoretical framework for the expressive ability of data re-uploading quantum neural networks.
  arXiv  Detail & Related papers  (2022-05-16T17:58:27Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  We theoretically characterize the impact of connectivity patterns on the convergence of deep neural networks (DNNs) under gradient descent training. We show that by a simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate.
  arXiv  Detail & Related papers  (2022-05-11T17:43:54Z)
• Bounding the Complexity of Formally Verifying Neural Networks: A Geometric Approach [1.9493449206135296]
  We consider formally verifying the complexity of ReLU Neural Networks (NNs) In this paper, we show that for two different NNs, the verification problem satisfies two different types of constraints. Both algorithms efficiently translate the NN parameters into the effect of the NN's architecture by means of hyperplanes.
  arXiv  Detail & Related papers  (2020-12-22T00:29:54Z)
• Toward Trainability of Quantum Neural Networks [87.04438831673063]
  Quantum Neural Networks (QNNs) have been proposed as generalizations of classical neural networks to achieve the quantum speed-up. Serious bottlenecks exist for training QNNs due to the vanishing with gradient rate exponential to the input qubit number. We show that QNNs with tree tensor and step controlled structures for the application of binary classification. Simulations show faster convergent rates and better accuracy compared to QNNs with random structures.
  arXiv  Detail & Related papers  (2020-11-12T08:32:04Z)
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks [80.55378250013496]
  We study how neural networks trained by gradient descent extrapolate what they learn outside the support of the training distribution. Graph Neural Networks (GNNs) have shown some success in more complex tasks.
  arXiv  Detail & Related papers  (2020-09-24T17:48:59Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  It is known that the current graph neural networks (GNNs) are difficult to make themselves deep due to the problem known as over-smoothing. Multi-scale GNNs are a promising approach for mitigating the over-smoothing problem. We derive the optimization and generalization guarantees of transductive learning algorithms that include multi-scale GNNs.
  arXiv  Detail & Related papers  (2020-06-15T17:06:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.