mlsanityData to 14 Oct 2026

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

arXiv 2512.12805 ↗First posted 14 Dec 2025cs.LG cs.AIcited by 1

Not on the map. Why?

Abstract (arXiv)

Transformers exhibit a notable property of 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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 42 of its 54 references that are in the map. First posted on arXiv 14 Dec 2025.

Builds on

42 of 54 references.

References · 42

  1. 2017Attention Is All You Needcited by 60,361
  2. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 30,186
  3. 2017Graph Attention Networkscited by 8,923
  4. 2016PointNet: Deep Learning on Point Sets for 3D Classification and Segmentationcited by 5,248
  5. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,703
  6. 2019Transformer-XL: Attentive Language Models Beyond a Fixed-Length Contextcited by 1,850
  7. 2020Point Transformercited by 1,470
  8. 2018Self-Attention with Relative Position Representationscited by 1,120
  9. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  10. 2023Point Transformer V3: Simpler, Faster, Strongercited by 589
  11. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
  12. 2021Do Transformers Really Perform Bad for Graph Representation?cited by 320
30 more
  1. 2022Exploring Length Generalization in Large Language Modelscited by 206
  2. 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
  3. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  4. 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 118
  5. 2022Particle Transformer for Jet Taggingcited by 98
  6. 2020Molecular representation learning with language models and domain-relevant auxiliary taskscited by 94
  7. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  8. 2024Transformers Can Achieve Length Generalization But Not Robustlycited by 86
  9. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 59
  10. 2021Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encodingcited by 51
  11. 2024A Formal Framework for Understanding Length Generalization in Transformerscited by 45
  12. 2021Transferability Properties of Graph Neural Networkscited by 43
  13. 2023On the Stability of Expressive Positional Encodings for Graphscited by 33
  14. 2023A graphon-signal analysis of graph neural networkscited by 30
  15. 2023Sequence Length Independent Norm-Based Generalization Bounds for Transformerscited by 29
  16. 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 24
  17. 2021Point Cloud Transformers applied to Collider Physicscited by 23
  18. 2024Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structurecited by 23
  19. 2024Comparing Graph Transformers via Positional Encodingscited by 20
  20. 2023Limits, approximation and size transferability for GNNs on sparse graphs via graphopscited by 18
  21. 2024Generalization Bounds for Message Passing Networks on Mixture of Graphonscited by 17
  22. 2025Extrapolation by Association: Length Generalization Transfer in Transformerscited by 13
  23. 2024Locality-Sensitive Hashing-Based Efficient Point Transformer with Applications in High-Energy Physicscited by 12
  24. 2022Convergence of Invariant Graph Networkscited by 9
  25. 2021Geometric Transformer for End-to-End Molecule Properties Predictioncited by 8
  26. 2023Predicting Hateful Discussions on Reddit using Graph Transformer Networks and Communal Contextcited by 8
  27. 2025The Role of Sparsity for Length Generalization in Transformerscited by 8
  28. 2024Enhancing Size Generalization in Graph Neural Networks through Disentangled Representation Learningcited by 7
  29. 2024Positional Attention: Expressivity and Learnability of Algorithmic Computationcited by 7
  30. 2025Higher-Order Graphon Neural Networks: Approximation and Cut Distancecited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Sharper Generalization Bounds for Transformercited by 3