Quantifying Neural Network Simplicity with Effective Degree: A Polynomial Approach

From "When Do Neural Networks Learn World Models?" to Measurable Simplicity

The article introduces a new method from a Tsinghua University team (ICML 2026) that quantifies and optimizes the simplicity of neural networks. The work builds on their ICML 2025 paper "When Do Neural Networks Learn World Models?" which formalized world-model learning as latent variable recovery and proved that a low-degree bias helps identify true latent variables under multi-task training with low-degree task distributions. That earlier analysis used Fourier-Walsh decomposition on Boolean functions, but it was difficult to apply directly to real-world architectures like ViTs, language models, or RL policies.

Why Measuring Simplicity Is Hard

Common complexity measures — parameter norms, loss-surface sharpness, Jacobian norms, linear-region counts, compression lengths — each satisfy only a subset of three desiderata: generality (architecture-agnostic), quantifiability (stable computation on large trained models), and optimizability (differentiable for use during training). Parameter-space metrics change under reparameterization without altering the function; function-space polynomial degree is natural but suffers from combinatorial explosion in high dimensions.

Polynomial Representation Along Data Paths

The core idea: instead of fitting a multivariate polynomial globally, observe the network along many one-dimensional interpolation paths between data samples. Given two samples x_a and x_b from the data distribution, define the path x(t) = (1-t)x_a + t x_b for t ∈ [0,1]. The network output f(x(t)) becomes a univariate function of t. Approximate this function with Chebyshev orthogonal polynomials:

f(x(t)) ≈ Σ_{k=0}^K c_k T_k(2t-1)

where T_k are Chebyshev polynomials and c_k are coefficients. Low-order coefficients capture linear/quadratic trends; high-order coefficients capture oscillations. Three practical designs ensure stability: (1) data-dependent paths concentrate measurement near the data manifold; (2) orthogonal polynomial bases with cosine sampling mitigate numerical instability; (3) optional per-path PCA on high-dimensional outputs reduces dimensionality before fitting.

Theory shows that for multivariate polynomials, random directions from a distribution with density almost surely preserve algebraic degree, so averaging over paths retains the correct complexity ordering.

Effective Degree (ED): A Stable, Continuous Complexity Measure

Strict algebraic degree only cares about the highest non-zero coefficient, making it brittle to tiny high-order terms. The authors define Effective Degree as a weighted average of polynomial orders:

ED = (Σ_k k |c_k|) / (Σ_k |c_k|)

A normalized version removes overall scale dependence. ED is continuous and stable w.r.t. coefficients. The final network-level ED averages over many sampled paths. This measure lives in function space (invariant to reparameterization) and is distribution-dependent (reflects complexity near the data).

ED Predicts Generalization Better Than Sharpness or Norms

On CIFAR-10 with 27 hyperparameter settings each for ResNet18 and ViT-Tiny, ED achieves Pearson correlation 0.99 with generalization gap (linear fit R² = 0.98). The best sharpness metric reaches 0.94 correlation ( R² = 0.88). On fine-tuning CLIP ViT-B/32 on ImageNet, ED maintains positive correlation with generalization gap, while sharpness, adaptive sharpness, and parameter norms show weak or even negative correlations.

Tracking the Memorization-to-Generalization Transition in Grokking

In grokking experiments (algorithmic datasets where models memorize then suddenly generalize), ED rises during memorization, peaks near the validation-loss drop, then falls as generalization emerges. Parameter norms increase monotonically throughout; sharpness metrics do not clearly mark the phase transition. This demonstrates ED can track the dynamics of a single model moving from memorization to rule learning.

Differentiable Simplicity Optimization via ED Regularization

Because polynomial fitting is a least-squares problem, coefficients have analytic gradients w.r.t. network outputs; ED can be backpropagated to parameters. The authors add ED as an explicit regularizer:

L_total = L_task + λ ED

This does not force strict linearity nor require interpolated labels; it merely penalizes unnecessary high-order variation, encouraging simpler functions that still satisfy the task. Experiments across supervised classification (images, text), CLIP fine-tuning, and reinforcement learning show consistent generalization improvements. In CLIP fine-tuning, ED-regularized models achieve better in-distribution/out-of-distribution trade-offs as the interpolation weight varies. In RL, ED regularization improves performance on several tasks.

Limitations and Failure Cases

The paper acknowledges that "simpler is better" is not unconditional. A failure case shows that if the simplest feature in the data is a non-robust shortcut, ED may prefer it just like a standard model. ED measures functional complexity, not causal correctness, semantic plausibility, or fairness. Aligning simplicity with the right inductive bias still requires task design, data structure, and architecture choices. Additionally, path-based polynomial fitting is a distribution-dependent proxy; sampling extra interpolation points during training adds computational overhead.

Summary and Outlook

Representation: Orthogonal polynomials on data-dependent interpolation paths compactly describe high-dimensional neural functions.

Measurement: Effective Degree stably quantifies high-order components and predicts generalization behavior.

Optimization: Differentiable polynomial fitting lets function simplicity enter the training objective directly.

Application: Consistent generalization gains in vision, language, vision-language, and RL.

Polynomial representations bridge theory and practice: "degree" enables theoretical analysis of world-model emergence; "effective degree" enables measurement and intervention in real deep networks. Open questions include ED dynamics across architectures/optimizers, using ED for checkpoint selection, diagnosing fine-tuning overfitting, designing self-supervised tasks for world models, and discovering other function-space representations with generality, computability, and differentiability.

References

[1] Zhang, T., Li, X., Xiao, M., Chen, G., & Chen, F. Quantifying and Optimizing Simplicity via Polynomial Representations. ICML, 2026. (https://arxiv.org/abs/2605.29823)

[2] Zhang, T., Chen, G., & Chen, F. When Do Neural Networks Learn World Models? ICML, 2025. (https://proceedings.mlr.press/v267/zhang25j.html)

[3] Klindt, D., LeCun, Y., & Balestriero, R. When Does LeJEPA Learn a World Model? arXiv preprint, 2026. (https://arxiv.org/abs/2605.26379)

[4] Nakkiran, P. et al. SGD on Neural Networks Learns Functions of Increasing Complexity. NeurIPS, 2019.

[5] Keskar, N. S. et al. On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima. ICLR, 2017.

[6] Power, A. et al. Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets. arXiv preprint, 2022.

Paper link: https://arxiv.org/abs/2605.29823

Code link: https://github.com/xinzaixinzai/Effective-Degree