From Small to Large: Generalization Bounds for Transformers on Variable-Size Inputs

• URL: http://arxiv.org/abs/2512.12805v1
• Date: Sun, 14 Dec 2025 19:02:16 GMT
• Title: From Small to Large: Generalization Bounds for Transformers on Variable-Size Inputs
• Abstract summary: Transformers exhibit a notable property of emphsize generalization, demonstrating an ability to extrapolate from smaller token sets to significantly longer ones.<n>This behavior has been documented across diverse applications, including point clouds, graphs, and natural language.<n>We develop a theoretical framework to analyze this phenomenon for geometric data.
• Score: 7.908162875769378
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Transformers exhibit a notable property of \emph{size generalization}, demonstrating an ability to extrapolate from smaller token sets to significantly longer ones. This behavior has been documented across diverse applications, including point clouds, graphs, and natural language. Despite its empirical success, this capability still lacks some rigorous theoretical characterizations. In this paper, we develop a theoretical framework to analyze this phenomenon for geometric data, which we represent as discrete samples from a continuous source (e.g., point clouds from manifolds, graphs from graphons). Our core contribution is a bound on the error between the Transformer's output for a discrete sample and its continuous-domain equivalent. We prove that for Transformers with stable positional encodings, this bound is determined by the sampling density and the intrinsic dimensionality of the data manifold. Experiments on graphs and point clouds of various sizes confirm the tightness of our theoretical bound.

Related papers

• When Do Graph Foundation Models Transfer? A Data-Centric Theory [68.54337055801571]
  Graph foundation models (GFMs) aim to reuse a single backbone across diverse graph domains, yet their transfer is often uneven and can exhibit negative transfer.<n>We show that for both set-based and message-passing tokenizations, any Lipschitz backbone admits an explicit decomposition of cross-domain output shift.<n>A key ingredient is positional-encoding (PE) stability: we establish stability guarantees for spectral PEs and highlight contrasting behaviors of eigenvector- versus subspace-based PEs.
  arXiv  Detail & Related papers  (2026-05-28T12:07:27Z)
• Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers [50.98108117044413]
  We show that the choice of a graph-to-token map is a fundamental component of transformer expressivity.<n>We examine three tokenizations that serve as building blocks for many existing graph tokenizations: spectral, random-walk, and adjacency tokenizations.
  arXiv  Detail & Related papers  (2026-05-21T13:32:20Z)
• GraViti: Graph-Level Variational Autoencoders with Relaxed Permutation Invariance [20.535256323518215]
  We introduce GraViti, a graph-level variational autoencoder that maps entire graphs to compact latent vectors.<n>On molecular benchmarks, GraViti learns to decode valid samples that follow the chemical constraints present in the training data.<n>GraViti achieves state-of-the-art reconstruction accuracy on large datasets, and provides solid generative performance.
  arXiv  Detail & Related papers  (2026-05-15T22:08:45Z)
• The calculus of variations of the Transformer on the hyperspherical tangent bundle [0.0]
  We offer a theoretical mathematical background to Transformers through Lagrangian optimization across the token space.<n>The Transformer, as a flow map, exists in the tangent fiber for each token along the high-dimensional unit sphere.<n>We derive the Euler-Lagrange equation for the Transformer.
  arXiv  Detail & Related papers  (2025-07-21T09:43:33Z)
• A Theory for Compressibility of Graph Transformers for Transductive Learning [6.298115235439078]
  Transductive tasks on graphs differ fundamentally from typical supervised machine learning tasks. All train/test/validation samples are present during training, making them more akin to a semi-supervised task. We establish some theoretical bounds on how and under what conditions the hidden dimension of these networks can be compressed.
  arXiv  Detail & Related papers  (2024-11-20T04:20:17Z)
• Graph Transformers Dream of Electric Flow [72.06286909236827]
  We show that the linear Transformer, when applied to graph data, can implement algorithms that solve canonical problems.<n>We present explicit weight configurations for implementing each algorithm, and we bound the constructed Transformers' errors by the errors of the underlying algorithms.<n>Our work is an initial step towards elucidating the inner-workings of the Transformer for graph data.
  arXiv  Detail & Related papers  (2024-10-22T05:11:45Z)
• Generating Graphs via Spectral Diffusion [48.70458395826864]
  We present GGSD, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process.<n>An extensive set of experiments on both synthetic and real-world graphs demonstrates the strengths of our model against state-of-the-art alternatives.
  arXiv  Detail & Related papers  (2024-02-29T09:26:46Z)
• Towards Understanding Inductive Bias in Transformers: A View From Infinity [9.00214539845063]
  We argue transformers tend to be biased towards more permutation symmetric functions in sequence space. We show that the representation theory of the symmetric group can be used to give quantitative analytical predictions. We argue WikiText dataset, does indeed possess a degree of permutation symmetry.
  arXiv  Detail & Related papers  (2024-02-07T19:00:01Z)
• A Hierarchical Spatial Transformer for Massive Point Samples in Continuous Space [11.074768589778934]
  Existing transformers are mostly designed for sequences (texts or time series), images or videos, and graphs. This paper proposes a novel transformer model for massive (up to a million) point samples in continuous space.
  arXiv  Detail & Related papers  (2023-11-08T02:54:19Z)
• Curve Your Attention: Mixed-Curvature Transformers for Graph Representation Learning [77.1421343649344]
  We propose a generalization of Transformers towards operating entirely on the product of constant curvature spaces. We also provide a kernelized approach to non-Euclidean attention, which enables our model to run in time and memory cost linear to the number of nodes and edges.
  arXiv  Detail & Related papers  (2023-09-08T02:44:37Z)
• Approximation and Estimation Ability of Transformers for Sequence-to-Sequence Functions with Infinite Dimensional Input [50.83356836818667]
  We study the approximation and estimation ability of Transformers as sequence-to-sequence functions with infinite dimensional inputs. Our theoretical results support the practical success of Transformers for high dimensional data.
  arXiv  Detail & Related papers  (2023-05-30T02:44:49Z)
• DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion [66.21290235237808]
  We introduce an energy constrained diffusion model which encodes a batch of instances from a dataset into evolutionary states. We provide rigorous theory that implies closed-form optimal estimates for the pairwise diffusion strength among arbitrary instance pairs. Experiments highlight the wide applicability of our model as a general-purpose encoder backbone with superior performance in various tasks.
  arXiv  Detail & Related papers  (2023-01-23T15:18:54Z)
• Convolutional Filtering on Sampled Manifolds [122.06927400759021]
  We show that convolutional filtering on a sampled manifold converges to continuous manifold filtering. Our findings are further demonstrated empirically on a problem of navigation control.
  arXiv  Detail & Related papers  (2022-11-20T19:09:50Z)
• Revisiting Over-smoothing in BERT from the Perspective of Graph [111.24636158179908]
  Recently over-smoothing phenomenon of Transformer-based models is observed in both vision and language fields. We find that layer normalization plays a key role in the over-smoothing issue of Transformer-based models. We consider hierarchical fusion strategies, which combine the representations from different layers adaptively to make the output more diverse.
  arXiv  Detail & Related papers  (2022-02-17T12:20:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.