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

Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement in these settings is size generalization: the ability of a model trained on inputs of one size to generalize reliably 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 the input dimension. Moreover, although extensive work has established when models on sets and graphs can be transferred across input sizes, such transferability 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. Toward this goal, 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, a standard condition in classical learning theory, is insufficient for efficient size generalization: while it yields generalization error $n^{-\Theta (1)}$ and hence polynomial sample complexity for in-domain learning, the error for size generalization decays only as $(\log n{)}^{-\Theta (1)}$, yielding an exponential separation in sample complexity. Thus, conditions sufficient for polynomial sample complexity in classical learning can require exponentially more samples when generalizing across input sizes. We then identify an exponential source condition under which size generalization achieves error $n^{-\Theta (1)}$, recovering polynomial sample complexity. All of these guarantees are independent of the input dimension and depend only on the number of training samples, yielding dimension-free scaling laws. We also provide matching minimax lower bounds, establishing the optimality of our results. 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.