aiqbench analysis
This paper provides statistical learning theory for size generalization, which asks whether a model trained on small sets or graphs can handle much larger ones. Its main claim is a sample-complexity gap: under polynomial source decay, size generalization error shrinks only as (log n)^-Θ(1), while an exponential source condition restores polynomial rates. For ML practitioners, the practical takeaway is that the assumptions about how inputs vary across sizes, not input dimension, largely determine the data cost of transferring across scales. These are theoretical bounds, so their impact depends on whether real-world source conditions resemble the ones analyzed.
Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation
arXiv:2610.19279v1 Announce Type: new Abstract: Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is \emph{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.
Abstract:Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is \emph{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.
32 pages, 1 figure. An extended abstract of this paper appeared at the ICML 2026 HiLD Workshop (July 10, 2026)
Machine Learning (cs.LG); Artificial Intelligence (cs.AI)
arXiv:2610.19279 [cs.LG]
(or arXiv:2610.19279v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.19279 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 372 words
Related coverage
Lattice-Based Cryptography Explained
Quantum Zeitgeist · Aug 15, 2026
Generalization and infinite width
LessWrong · Aug 1, 2026
The Entangled Dimensions of Decision Theory
LessWrong · Jul 30, 2026
Synthesis Superintelligence: from Semiconductors to Superconductors — Periodic Labs’ Liam Fedus and Ekin Dogus Cubuk
Latent Space · Oct 8, 2026