# Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation

arXiv: https://arxiv.org/abs/2610.19279 · HTML: https://mlsanity.com/paper/2610.19279/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 61 of its 76 references that are in the map.
- First posted on arXiv 13 Oct 2026.

## Builds on (most cited first, 30 of 61)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [E(n) Equivariant Graph Neural Networks](https://mlsanity.com/paper/2102.09844/) (2021)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Frame Averaging for Invariant and Equivariant Network Design](https://mlsanity.com/paper/2110.03336/) (2021)
- [Incorporating Symmetry into Deep Dynamics Models for Improved Generalization](https://mlsanity.com/paper/2002.03061/) (2020)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [Lorentz Group Equivariant Neural Network for Particle Physics](https://mlsanity.com/paper/2006.04780/) (2020)
- [Graphon Neural Networks and the Transferability of Graph Neural Networks](https://mlsanity.com/paper/2006.03548/) (2020)
- [Equivariance with Learned Canonicalization Functions](https://mlsanity.com/paper/2211.06489/) (2022)
- [Transferability of Spectral Graph Convolutional Neural Networks](https://mlsanity.com/paper/1907.12972/) (2019)
- [On the Limitations of Representing Functions on Sets](https://mlsanity.com/paper/1901.09006/) (2019)
- [A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks](https://mlsanity.com/paper/2012.07690/) (2020)
- [Size-Invariant Graph Representations for Graph Classification Extrapolations](https://mlsanity.com/paper/2103.05045/) (2021)
- [SO(2)-Equivariant Reinforcement Learning](https://mlsanity.com/paper/2203.04439/) (2022)
- [Molecular graph generation with Graph Neural Networks](https://mlsanity.com/paper/2012.07397/) (2020)
- [Convergence and Stability of Graph Convolutional Networks on Large Random Graphs](https://mlsanity.com/paper/2006.01868/) (2020)
- [Theory for Equivariant Quantum Neural Networks](https://mlsanity.com/paper/2210.08566/) (2022)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [Transferability of Graph Neural Networks: an Extended Graphon Approach](https://mlsanity.com/paper/2109.10096/) (2021)
- [Approximation-Generalization Trade-offs under (Approximate) Group Equivariance](https://mlsanity.com/paper/2305.17592/) (2023)
- [Softmax is not Enough (for Sharp Size Generalisation)](https://mlsanity.com/paper/2410.01104/) (2024)
- [Transferability Properties of Graph Neural Networks](https://mlsanity.com/paper/2112.04629/) (2021)
- [Equivariant Frames and the Impossibility of Continuous Canonicalization](https://mlsanity.com/paper/2402.16077/) (2024)
- [Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks](https://mlsanity.com/paper/2210.01906/) (2022)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks](https://mlsanity.com/paper/2207.07888/) (2022)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)

## Abstract (arXiv)

Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is size generalization: the ability of a model trained on inputs of one size to generalize to inputs of a different, potentially much larger, size. Classical statistical learning theory, however, primarily considers fixed input domains, and its guarantees often deteriorate with input dimension. Although extensive work has established when models on sets and graphs can be transferred across input sizes, such results do not characterize the statistical cost of doing so: the sample complexity of size generalization, and its relationship to classical in-domain learning, remain largely unknown. We develop a statistical learning theory of size generalization and establish a sharp exponential separation in sample complexity. Letting n denote the number of training samples, we show that polynomial source decay is insufficient for efficient size generalization: while it yields error n-Theta(1) and hence polynomial sample complexity for in-domain learning, size-generalization error decays only as (log n)-Theta(1), yielding an exponential separation. Thus, polynomial in-domain sample complexity can become exponential across sizes. We then identify an exponential source condition under which size generalization achieves error n-Theta(1), recovering polynomial sample complexity. These guarantees are independent of input dimension and depend only on the number of training samples, yielding dimension-free scaling laws. We also provide matching minimax lower bounds, establishing optimality. To our knowledge, this work provides the first dimension-free minimax theory of size generalization and a rigorous characterization of when, and at what statistical cost, learning can transfer across input sizes.