From the 2 of 7 linked papers with an AI index.
5 papers · 1 filter
From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP
Michael Rizvi-Martel, Satwik Bhattamishra, Guillaume Rabusseau +1
The paper derives preliminary sample complexity bounds for learning C‑RASP constructions with Transformer models, linking their expressive power to learnability.
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…
Discovering Interpretable Algorithms by Decompiling Transformers to RASP
Xinting Huang, Aleksandra Bakalova, Satwik Bhattamishra +2
Recent work has shown that the computations of Transformers can be simulated in the RASP family of programming languages. These findings have enabled improved understanding of the…
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…