تقرير
Understanding Transformer Reasoning Capabilities via Graph Algorithms
| العنوان: | Understanding Transformer Reasoning Capabilities via Graph Algorithms |
|---|---|
| المؤلفون: | Sanford, Clayton, Fatemi, Bahare, Hall, Ethan, Tsitsulin, Anton, Kazemi, Mehran, Halcrow, Jonathan, Perozzi, Bryan, Mirrokni, Vahab |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science |
| مصطلحات موضوعية: | Computer Science - Machine Learning, Computer Science - 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. Comment: 43 pages, 8 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2405.18512 |
| رقم الأكسشن: | edsarx.2405.18512 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |