Tight Asymptotic Bounds on the Maximum Number of Linear Regions of Piecewise-Linear Kolmogorov--Arnold networks

Ye Su, Yong LiuarXiv 2026 · arXiv

TL;DR

This paper provides the first tight mathematical bounds on the "expressive capacity" of Piecewise-Linear Kolmogorov–Arnold Networks (KANs) by counting their maximum number of linear regions. The authors prove that KANs offer a significant polynomial advantage in geometric complexity over standard ReLU networks when both are restricted to the same number of parameters and layers.

What Problem Does This Paper Address?

In the world of deep learning, we often measure a model's "expressive power" by how many linear regions it can create. Think of a neural network as a complex origami project: the more folds (linear regions) it can make in the input space, the more intricate the patterns it can recognize.

Recently, Kolmogorov–Arnold Networks (KANs) have emerged as a buzzy alternative to standard Multi-Layer Perceptrons (MLPs). While we have a good grasp of how ReLU-based MLPs scale, our understanding of KANs has been fuzzy. Previous research provided an upper bound on KAN complexity that was "loose"—essentially overestimating their power—and lacked a lower bound entirely. This paper closes that gap, providing a precise "yardstick" to measure exactly how complex a KAN can get compared to its ReLU cousins.

Methods

The authors employ a rigorous theoretical framework based on hyperplane arrangements. They analyze two specific types of Continuous Piecewise-Linear (CPWL) KANs:

  1. Edge-wise-knot: Every connection (edge) between nodes can have its own unique "bends" (knots).
  2. Source-shared-knot: A more restricted version where all edges coming from the same source node share the same knot locations.

The core of their proof involves:

  • Parallel Hyperplane Analysis: Recognizing that knots from the same source node create parallel "cuts" in the input space, which limits the total number of regions more than previously thought.
  • Effective Dimension ($\rho$): They account for "bottlenecks" in the network. If a middle layer is very narrow, it limits the number of independent directions available for subsequent layers to divide the space.
  • Inductive Proofs: They build the bounds layer-by-layer to show how complexity compounds through the network's depth.

Datasets

Not discussed in the paper. This is a purely theoretical mathematical analysis; no empirical training or benchmarking on datasets was performed.

Key Insights and Ideas

  • The "Parallelism" Correction: Previous bounds treated every edge in a KAN as if it could cut the space in a completely unique direction. The authors realized that because edges from the same node share an input coordinate, their "cuts" are parallel. This insight is what allowed them to tighten the upper bound significantly.
  • Bottlenecks Matter: The complexity isn't just about the current layer's width; it's limited by the narrowest preceding layer. They formalize this using "effective dimension" ($\rho_{\ell-1}$), which dictates the actual growth rate of regions.
  • Parameter Efficiency: KANs can increase their complexity by adding more "knots" (local segments) to existing edges. In contrast, increasing the complexity of a ReLU network usually requires adding more neurons, which quadratically increases the number of connections (parameters). This makes KANs fundamentally more efficient at generating geometric complexity.

Key Results

  • Tight Bounds Established: The authors proved the tight growth order for KAN regions is $\Theta_{\mathbf{n}}(k^{\sum_{\ell=1}^{T}\rho_{\ell-1}})$, where $k$ is the number of segments per edge.
  • Massive Improvement: Their new bound improves upon previous estimates by a factor of $k$ raised to a power proportional to the network's width. In one example (a 2-layer network), the old bound predicted 1,000,000 regions, while the new tight bound showed the true maximum is closer to 36,100.
  • The KAN Advantage: When comparing a KAN and a ReLU network with the same number of parameters ($\Lambda$) and depth ($T$), the KAN can produce significantly more linear regions. Specifically, the ratio of KAN regions to ReLU regions grows as $\Lambda^{d\lfloor T/2\rfloor}$. For a standard 2-layer setup, this represents a polynomial advantage that grows with the parameter budget.

Limitations and Future Work

  • Maximum vs. Average: The paper focuses on the maximum possible number of regions. In practice, a trained network might use far fewer regions, or the regions might be distributed in a way that doesn't help with the specific task.
  • Dense Parameterization: The comparison assumes "dense" networks. The scaling might change for sparse architectures.
  • Beyond Piecewise-Linear: While this paper covers CPWL KANs (which are common), many KAN implementations use smooth splines. Extending these tight bounds to non-linear, smooth edge functions remains an open challenge.
  • Optimization: The paper proves KANs can represent more complex functions, but it doesn't address whether they are easier or harder to train using gradient descent compared to ReLU networks.

Summary updated

Abstract

Schoots et al.~\citep{schoots2025relating} (AISTATS 2025) established a generally loose upper bound on the number of linear regions of continuous piecewise-linear (CPWL) Kolmogorov--Arnold networks (KANs), without providing a lower bound. We consider a $T$-layer network with width vector $\mathbf n=(n_0,\ldots,n_T)$, input dimension $n_0=d$, output width $n_T=1$, and at most $k\geq2$ affine segments per edge. Our matching upper and lower bounds determine the tight growth order $Θ_{\mathbf n}(k^{\sum_{\ell=1}^{T}ρ_{\ell-1}})$ in $k$, where $ρ_{\ell-1}:=\min_{0\leq s\leq\ell-1}n_s$. When every hidden width is at least $d$, the tight order simplifies to $Θ_{\mathbf n}(k^{dT})$. The upper bound of \citep{schoots2025relating} is $k^{\sum_{\ell=1}^{T}n_{\ell-1}n_\ell}$. Our upper bound improves it by a factor of $Θ_{\mathbf n}\!\left(k^{\sum_{\ell=1}^{T}n_{\ell-1}n_\ell-\sum_{\ell=1}^{T}ρ_{\ell-1}} \right)$, with strict asymptotic improvement whenever a hidden layer has width greater than one. We further compare CPWL KANs with rectified linear unit (ReLU) networks using dense parameterizations with at most $Λ$ parameters per model and the same fixed nonlinear depth $T$. Counting trainable knot locations and optimizing the widths and $k$, we prove that the maximum region count of CPWL KANs divided by that of ReLU networks is $Θ_{d,T}(Λ^{d\lfloor T/2\rfloor})$ as $Λ\to\infty$, yielding a polynomial advantage for KANs when $T\geq2$. These tight bounds characterize the attainable geometric complexity of CPWL KANs, providing a foundation for understanding their expressive power and guiding architectural design.
BibTeX
@misc{su2026tight,
  author = {Ye Su and Yong Liu},
  title = {{Tight Asymptotic Bounds on the Maximum Number of Linear Regions of Piecewise-Linear Kolmogorov--Arnold networks}},
  year = {2026},
  eprint = {2611.07973},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.07973},
}
Figure