4 papers
Depth-Width tradeoffs in Algorithmic Reasoning of Graph Tasks with Transformers
Gilad Yehudai, Clayton Sanford, Maya Bechler-Speicher +3
Transformers have revolutionized the field of machine learning. In particular, they can be used to solve complex algorithmic problems, including graph-based tasks. In such algorith…
Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers
Maya Bechler-Speicher, Gilad Yehudai, Gil Harari +3
Transformers have become a central architecture for graph learning, but their application to graphs requires first choosing a tokenization: a graph-to-token map that determines whi…
Best of Both Worlds: Advantages of Hybrid Graph Sequence Models
Ali Behrouz, Ali Parviz, Mahdi Karami +3
Modern sequence models (e.g., Transformers, linear RNNs, etc.) emerged as dominant backbones of recent deep learning frameworks, mainly due to their efficiency, representational po…
Understanding Transformer Reasoning Capabilities via Graph Algorithms
Clayton Sanford, Bahare Fatemi, Ethan Hall +5
Which transformer scaling regimes are able to perfectly solve different classes of algorithmic problems? While tremendous empirical advances have been attained by transformer-based…