Understanding Transformer Reasoning Capabilities via Graph Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914815414370304 |
|---|---|
| author | Sanford, Clayton Fatemi, Bahare Hall, Ethan Tsitsulin, Anton Kazemi, Mehran Halcrow, Jonathan Perozzi, Bryan Mirrokni, Vahab |
| author_facet | Sanford, Clayton Fatemi, Bahare Hall, Ethan Tsitsulin, Anton Kazemi, Mehran Halcrow, Jonathan Perozzi, Bryan Mirrokni, Vahab |
| contents | Which transformer scaling regimes are able to perfectly solve different classes of algorithmic problems? While tremendous empirical advances have been attained by transformer-based neural networks, a theoretical understanding of their algorithmic reasoning capabilities in realistic parameter regimes is lacking. We investigate this question in terms of the network's depth, width, and number of extra tokens for algorithm execution. Our novel representational hierarchy separates 9 algorithmic reasoning problems into classes solvable by transformers in different realistic parameter scaling regimes. We prove that logarithmic depth is necessary and sufficient for tasks like graph connectivity, while single-layer transformers with small embedding dimensions can solve contextual retrieval tasks. We also support our theoretical analysis with ample empirical evidence using the GraphQA benchmark. These results show that transformers excel at many graph reasoning tasks, even outperforming specialized graph neural networks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18512 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Understanding Transformer Reasoning Capabilities via Graph Algorithms Sanford, Clayton Fatemi, Bahare Hall, Ethan Tsitsulin, Anton Kazemi, Mehran Halcrow, Jonathan Perozzi, Bryan Mirrokni, Vahab Machine Learning Artificial Intelligence Which transformer scaling regimes are able to perfectly solve different classes of algorithmic problems? While tremendous empirical advances have been attained by transformer-based neural networks, a theoretical understanding of their algorithmic reasoning capabilities in realistic parameter regimes is lacking. We investigate this question in terms of the network's depth, width, and number of extra tokens for algorithm execution. Our novel representational hierarchy separates 9 algorithmic reasoning problems into classes solvable by transformers in different realistic parameter scaling regimes. We prove that logarithmic depth is necessary and sufficient for tasks like graph connectivity, while single-layer transformers with small embedding dimensions can solve contextual retrieval tasks. We also support our theoretical analysis with ample empirical evidence using the GraphQA benchmark. These results show that transformers excel at many graph reasoning tasks, even outperforming specialized graph neural networks. |
| title | Understanding Transformer Reasoning Capabilities via Graph Algorithms |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2405.18512 |