5 papers
Algebraic Decomposition Theory for Transformer Length Generalization
Andy Yang, Blerta Veseli, Corentin Barloy +5
Transformer-based language models are known to sometimes generalize to sequences longer than seen during training, but we lack a precise characterization of which tasks admit lengt…
From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP
Michael Rizvi-Martel, Satwik Bhattamishra, Guillaume Rabusseau +1
A theoretical understanding of Transformers is crucial to better understand the capacities and limitations of large language models (LLMs). There is much work analyzing the express…
Understanding the Parameter Space Geometry of Transformers Encoding Boolean Functions
Blanka Köver, Alexandra Butoi, Anej Svete +2
Transformers consistently fail to learn certain simple functions that are provably expressible with specific parameter settings. This gap between learnability and expressivity is p…
Provably Learning Attention with Queries
Satwik Bhattamishra, Kulin Shah, Michael Hahn +1
We study the problem of learning Transformer-based sequence models with black-box access to their outputs. In this setting, a learner may adaptively query the oracle with any seque…
A Formal Framework for Understanding Length Generalization in Transformers
Xinting Huang, Andy Yang, Satwik Bhattamishra +5
A major challenge for transformers is generalizing to sequences longer than those observed during training. While previous works have empirically shown that transformers can either…