🤖 machine learning

Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexity

This paper investigates the gap between theoretical and realized expressivity in piecewise-affine neural networks by establishing a rigorous upper bound on affine regions along line segments and demonstrating that increasing task complexity paradoxically leads to "expressivity saturation," where trained models utilize significantly fewer affine regions than their architectural capacity allows, often resulting in degraded decision boundaries.

Original authors: Xuan Qi, Yi Wei, Fanqi Yu, Manuel Lecha

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xuan Qi, Yi Wei, Fanqi Yu, Manuel Lecha

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

The Big Idea: The "Unused Toolbox" Phenomenon

Imagine you buy a massive, high-end toolbox filled with thousands of specialized tools. You expect that if you give yourself a very difficult job (like building a complex clock), you will use almost every single tool in that box.

This paper discovers something surprising: When the job gets extremely hard, you might actually use fewer tools than when the job is easy.

The authors call this "Expressivity Saturation." It's a fancy way of saying that even though a neural network (a type of AI) has the theoretical ability to create a wildly complex solution, when the task becomes too chaotic or difficult, the network often settles for a much simpler, "collapsed" solution that uses far fewer of its internal capabilities.

The Two Main Experiments

The researchers looked at this problem from two different angles: a theoretical "one-dimensional" view and a practical "2D/3D" view.

1. The "String of Beads" Theory (1D Probes)

The Analogy: Imagine the neural network is a long string of beads. If you run a laser beam (a straight line) through this string, the laser hits different beads. Each time it hits a bead that changes its state, the laser beam gets "cut" into a new segment.

The Theory: The authors proved a strict rule: The number of segments the laser can be cut into depends entirely on how many beads (neurons) are in the string and how many "switches" each bead has.
The Finding: They calculated the maximum number of cuts possible. However, when they actually trained the network to solve a problem, the number of cuts was often much lower than the maximum.
The Lesson: Just because the string could be cut into 1,000 pieces doesn't mean it will be. If the pattern you are trying to learn is too messy, the network might not even try to use all its potential cuts.

2. The "Mosaic Floor" Experiment (2D and 3D)

The Analogy: Imagine the input data is a floor, and the neural network is an artist trying to paint a mosaic on it. The artist has a huge supply of tiles (affine regions).

Easy Task: If the picture is simple (like a clear smiley face), the artist uses many tiles to create a detailed, intricate mosaic.
Hard Task: Now, imagine the artist is told to paint a picture based on random noise (like static on an old TV). There is no real pattern to follow.
The Surprise: Instead of using more tiles to try to capture every tiny speck of noise, the artist actually uses fewer tiles. They stop trying to make a detailed mosaic and just paint a few large, blurry patches.

What the Data Showed:
The researchers trained AI models on random data with increasing amounts of "noise" (more samples).

Small amount of noise: The model used a moderate number of regions to learn.
Huge amount of noise: The model's "region count" crashed. It stopped creating complex boundaries.
The Result: In the hardest scenarios, the model didn't just fail to learn; it physically simplified its internal structure, collapsing its complex decision-making boundaries into a few large, ineffective shapes.

Why Does This Happen? (The "Saturation" Effect)

The paper suggests that when a task becomes too complex (like trying to memorize random noise), the optimization process (the training) hits a wall.

Think of it like a hiker trying to navigate a mountain range:

Easy Terrain: The hiker can take many winding paths, exploring every valley and peak (high region usage).
Impossible Terrain: If the terrain is a chaotic, shifting fog, the hiker stops trying to map every detail. Instead, they just pick a few broad directions and stop moving. They "saturate" their ability to explore.

The network isn't "smart" enough to realize that the task is impossible, so it gives up on complexity and settles for a simple, low-effort solution. This leads to degraded decision boundaries—the line the AI draws to separate "yes" from "no" becomes messy and ineffective.

Summary of Key Takeaways

Capacity $\neq$ Usage: Just because a neural network is built to be super complex (has a high "theoretical capacity"), it doesn't mean it will actually use that complexity.
Complexity Kills Complexity: Paradoxically, making the training data harder (more random samples) can cause the network to use fewer of its internal "switches" and "regions."
The Collapse: In the most difficult scenarios, the network's internal map of the world collapses. It stops refining its details and reverts to a crude, simple shape, which often leads to poor performance.
The Gap: There is a huge gap between what a network can do (theory) and what it actually does after training (reality), especially when the task is very hard.

In a nutshell: The paper shows that when you push an AI too hard with chaotic data, it doesn't get more creative; it gets simpler, giving up on its potential to be complex.

Technical Summary: Expressivity Saturation: Reduced Affine Region Usage Under Increasing Task Complexity

Problem Statement
Piecewise-affine neural networks (PANNs), such as those utilizing ReLU or LeakyReLU activations, define continuous piecewise-affine (CPWA) maps where the input space is partitioned into affine regions. While the number of these regions serves as a natural proxy for a network's expressive capacity, a significant gap exists between the theoretical worst-case capacity (often derived from combinatorial bounds) and the actual number of affine regions realized after training. This discrepancy is particularly critical when the input–label relation is highly complex. The paper investigates whether, under fixed architectures and training protocols, increasing the complexity of the task (specifically via random labels and increasing sample size) leads to a reduction in the number of realized affine regions, a phenomenon the authors term expressivity saturation.

Methodology
The authors employ a dual approach combining rigorous theoretical analysis on one-dimensional (1D) probes and exact empirical enumeration in bounded domains of higher dimensions (2D and 3D).

Theoretical Analysis (1D Probes):
- The authors define an affine line-segment probe $\gamma: [0, 1] \to \mathbb{R}^d$ .
- They derive a deterministic, architecture-dependent upper bound on the number of affine pieces ( $\alpha(f; \gamma)$ ) a CPWA MLP can realize along such a probe. This bound is a product of layer-wise width terms and activation breakpoint factors.
- From this, they derive a neuron-threshold lower bound, establishing the minimum architectural capacity required to represent a target function with a prescribed 1D piece complexity.
- They introduce metrics for realized region efficiency ( $\eta_{norm}$ ) and regions-per-neuron statistics to quantify the gap between theoretical capacity and actual usage.
Empirical Enumeration (2D and 3D):
- To move beyond 1D probes, the authors develop algorithms for exact bounded-domain enumeration.
- Algorithm 1 performs exact counting of affine pieces along 1D line probes by propagating interval partitions through network layers.
- Algorithm 2 exhaustively traverses all affine cells intersecting a prescribed compact domain $\Omega$ (e.g., $[-1, 1]^d$ ) in 2D and 3D. This involves identifying feasible seeds, recovering local affine descriptors, and traversing boundary-crossing operations to enumerate the set of realized regions $R_\Omega(f)$ .
- Experiments utilize fully-connected ReLU MLPs trained on random-label datasets with varying sample sizes to serve as a controlled proxy for increasing task complexity.

Key Contributions

Rigorous 1D Capacity Bound: The paper proves a deterministic upper bound on the number of affine pieces realizable along any affine line-segment probe for CPWA MLPs. This yields a corollary providing a necessary neuron-threshold lower bound for representing targets with specific 1D piece complexity.
Evidence of Expressivity Saturation: Through exact enumeration in 2D and 3D, the authors demonstrate that for fixed architectures and training protocols, increasing task complexity (via random labels and sample size) can sharply reduce the number of realized affine regions within a bounded domain. This occurs despite the architecture's worst-case theoretical capacity remaining unchanged.
Geometric and Dynamical Link: The study provides visual and quantitative evidence linking the collapse of realized affine regions to the failure of forming effective decision boundaries. In the most challenging regimes (e.g., high sample sizes with random labels), the reduction in region usage coincides with degraded decision boundary geometry.

Results

1D Consistency: Exact counting along probes confirms that the realized number of affine pieces is consistently far below the theoretical worst-case upper bound, even at random initialization. The "regions-per-neuron" statistic remains within a modest range but collapses when task complexity exceeds the effective capacity of the fixed architecture.
2D/3D Saturation: In experiments with fixed ReLU MLPs (e.g., $[32, 32, 32]$ $[32, 32, 32]$ ) and random labels:
- For small sample sizes, the number of realized regions tends to grow during training.
- For large sample sizes (e.g., 5,000 to 10,000), the number of realized regions drops sharply during training, often falling below the initialization level.
- This "collapse" is robust across different optimizers (Adam vs. SGD) and initialization schemes (Xavier).
Decision Boundaries: Visualizations show that in regimes where region usage collapses (high complexity), the network fails to form effective decision boundaries, whereas on learnable datasets (e.g., make_moons), region refinement correlates with boundary alignment.

Significance and Scope
The paper claims that nominal worst-case expressive capacity is an incomplete proxy for the nonlinear structure actually realized after training. The concept of expressivity saturation suggests that in controlled low-dimensional settings, increasing task complexity does not necessarily lead to richer partitioning; instead, it may lead to a reduction in utilized regions and poor classification geometry.

The authors explicitly note limitations:

The theoretical results are restricted to 1D probes and do not directly characterize full-dimensional region geometry.
Exact enumeration is computationally constrained to low dimensions (2D/3D) and moderate architectures due to the NP- and #P-hardness of affine-region counting in general.
The findings are based on fully-connected ReLU MLPs and random-label regimes; they do not yet establish how these phenomena manifest in structured data, real-world applications, or more complex architectures (e.g., CNNs, Transformers).

The work serves as a foundational step in linking input-label complexity to realized region usage, offering a new perspective on the gap between expressive capacity and expressive utilization.