Tractability via Low Dimensionality: The Parameterized Complexity of Training Quantized Neural Networks

Robert Ganian, Frank Sommer, Manuel SorgeICLR 2026 · OpenReview

TL;DR

Training quantized neural networks (where weights and data are integers) is generally NP-hard, even for incredibly simple architectures. However, this paper proves that training becomes "fixed-parameter tractable" (efficiently solvable) when the input dimensionality is low and the network structure is "tree-like" (low treewidth).

What Problem Does This Paper Address?

In modern AI, "quantization"—restricting neural network weights and activations to low-bit integers (like 4-bit or even binary)—is a standard trick to make models run faster on mobile phones and edge devices. While the practical benefits are clear, our theoretical understanding of the complexity of training these networks has lagged behind.

Formal definition of the d-QNNT problem

Most existing theory focuses on real-valued networks, where training is known to be $\exists\mathbb{R}$-complete (a complexity class even harder than NP). Quantized training is technically "easier" (it sits in NP), but that doesn't mean it's efficient. The authors aim to map out the "complexity landscape" of quantized training: under what specific structural constraints (width, depth, input size) does the problem move from "impossible to solve exactly" to "tractable"?

Methods

The authors employ the framework of Parameterized Complexity. Instead of just asking if a problem is "hard" based on the total input size, they look at specific parameters (like the number of inputs $\alpha$, the width of the layers, or the error bound $\ell$) to see if fixing those values makes the problem solvable in polynomial time.

Their approach combines two main pillars:

  1. Hardness Reductions: They use classic problems like Exact Set Cover, Hitting Set, and 3-SAT to prove that training remains NP-hard even when you restrict the network to be very shallow or very narrow.
  2. Algorithmic Design via Steinitz’ Lemma: To find positive results, they use a deep geometric result called Steinitz’ Lemma. They prove a structural insight: if a quantized network can be trained to zero error, there must exist a "sparse" version of that network where each neuron only has a bounded number of active incoming connections. This allows them to design a Dynamic Programming algorithm that traverses a "tree decomposition" of the network architecture.

Theoretical Framework & Proof Construction

As a theoretical "pen-and-paper" complexity study, this work does not use empirical datasets like ImageNet or MNIST. Instead, it uses mathematically constructed "gadgets" to prove its theorems. The "data" in their proofs consists of multisets of $d$-quantized vectors designed to force the neural network to behave like a logic gate or a set-covering mechanism.

Key Insights and Ideas

  • Quantization is a Double-Edged Sword: While quantization moves the problem from the exotic $\exists\mathbb{R}$ class into NP, the authors show that hardness is incredibly "sticky." You can't make the problem easy just by limiting the depth or width alone.
  • The Bottleneck is Dimensionality: The most significant finding is that high-dimensional input data is the primary source of hardness. If you have a massive number of input features, training is hard even for a single neuron.
  • Treewidth over Width: In graph theory, "treewidth" measures how much a graph looks like a tree. The authors show that we don't need the network to be narrow (low width) in every layer; we just need it to be "tree-like." This is a much more general and powerful result for real-world architectures that might have occasional wide layers.
  • The Sparsity Guarantee: The use of Steinitz’ Lemma to prove that "solutions can always be made sparse" is the paper's most elegant technical contribution. It provides a theoretical justification for why we might expect to find good quantized models even when the search space seems overwhelming.

Key Results

The paper provides a comprehensive "mindmap" of results detailing the boundaries of tractability:

Complexity landscape of quantized neural network training
  • Hardness: Training is NP-hard even for binary networks with zero hidden layers (Theorem 1) or networks with only two inputs and one hidden layer (Theorem 4).
  • Tractability: The problem is Fixed-Parameter Tractable (FPT) when parameterized by:
  • Input dimensionality + Treewidth + Output dimensionality ($\alpha + \text{tw} + \omega$).
  • Input dimensionality + Treewidth + Error bound ($\alpha + \text{tw} + \ell$).
  • Practical Implication: For tasks with naturally low-dimensional inputs (like certain sensor data or physics-based models), exact optimal training of quantized networks is theoretically possible, provided the architecture isn't too "tangled."

Limitations and Future Work

The authors identify a major remaining "white spot" on their map: Is training tractable if we only limit the input and output dimensionality ($\alpha + \omega$)? In other words, if the data is low-dimensional, can we efficiently train a network with an arbitrarily complex, "non-tree-like" architecture?

Additionally, while the algorithms provided are "tractable" in a mathematical sense (FPT), the constant factors involved in the $f(k)$ term are likely too large for immediate practical use. Future work could focus on refining these bounds to create more efficient empirical training heuristics inspired by these theoretical guarantees.

Summary updated

Abstract

The training of neural networks has been extensively studied from both algorithmic and complexity-theoretic perspectives, yet recent results in this direction almost exclusively concern real-valued networks. In contrast, advances in machine learning practice highlight the benefits of quantization, where network parameters and data are restricted to finite integer domains, yielding significant improvements in speed and energy efficiency. Motivated by this gap, we initiate a systematic complexity-theoretic study of ReLU Neural Network Training in the full quantization mode. We establish strong lower bounds by showing that hardness already arises in the binary setting and under highly restrictive structural assumptions on the architecture, thereby excluding parameterized tractability for natural measures such as depth and width. On the positive side, we identify nontrivial fixed-parameter tractable cases when parameterizing by input dimensionality in combination with width and either output dimensionality or error bound, and further strengthen these results by replacing width with the more general treewidth.
BibTeX
@inproceedings{ganian2026tractability,
  author = {Robert Ganian and Frank Sommer and Manuel Sorge},
  title = {{Tractability via Low Dimensionality: The Parameterized Complexity of Training Quantized Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2026},
  url = {https://openreview.net/forum?id=BAQNrsr987},
}
Figure