5 papers
On the Ability of Transformers to Verify Plans
Yash Sarrof, Yupei Du, Katharina Stein +3
Transformers have shown inconsistent success in AI planning tasks, and theoretical understanding of when generalization should be expected has been limited. We take important steps…
Barriers to Universal Reasoning With Transformers (And How to Overcome Them)
Oliver Kraus, Yash Sarrof, Yuekun Yao +2
Chain-of-Thought (CoT) has been shown to empirically improve Transformers' performance, and theoretically increase their expressivity to Turing completeness. However, whether Trans…
The Expressive Capacity of State Space Models: A Formal Language Perspective
Yash Sarrof, Yana Veitsman, Michael Hahn
Recently, recurrent models based on linear state space models (SSMs) have shown promising performance in language modeling (LM), competititve with transformers. However, there is l…
Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities
Mayank Jobanputra, Yana Veitsman, Yash Sarrof +4
Transformers have theoretical limitations in modeling certain sequence-to-sequence tasks, yet it remains largely unclear if these limitations play a role in large-scale pretrained…
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…