Elamur Research⌕
☰
home / papers / 2024 / Understanding Transformer Reasoning Capabilities via Graph Algorithms

Understanding Transformer Reasoning Capabilities via Graph Algorithms

Paper · 2024 · Clayton Sanford, Bahare Fatemi, Ethan Hall et al.

Summary

The paper asks which transformer sizes and shapes can exactly solve different algorithmic problems on graphs. Theory for realistic parameter settings has lagged well behind practice here. Each graph is given to a standard transformer as a token sequence of vertices, edges and a task query. The authors model the transformer as a communication protocol whose attention has limited bandwidth. Using this view, they build a hierarchy that sorts nine graph tasks by the depth, embedding width and number of blank "pause" tokens required.

Retrieval tasks fit into one layer with very small width. Parallelizable tasks such as connectivity need logarithmic depth, and that depth is also enough. Search tasks such as shortest path need considerably wider networks.

Experiments on the GraphQA benchmark support the theory:

  • Trained transformers beat GNNs on tasks that depend on long-range structure.
  • GNNs keep an advantage on local tasks when training data is scarce.
  • Small task-trained transformers far outperform prompted LLMs.

The work connects classical complexity classes to practical scaling choices for transformers.

Key points

  • The four scaling regimes are:
    • Depth1 (D1): one layer, m = O(log N).
    • LogDepth (LD): L = O(log N), m = O(N^ε).
    • LogDepthPause (LDP): LD plus up to poly(N) pause tokens.
    • LogDepthWide (LDW): log depth, width around O(N^{1/2+ε}).
  • Tasks map to regimes as follows:
    • D1 covers counting the nodes, counting the edges, checking whether a given edge is present, and finding a node's degree.
    • Connectivity falls in LD.
    • Cycle check and bipartiteness fall in LDP∩LDW.
    • Shortest path and diameter fall in LDW.
  • Logarithmic depth is proven both necessary and sufficient for connectivity-type tasks. Single-layer models cannot handle parallelizable or search tasks.
  • On GraphQA, a 60M transformer trained on 100K examples scores 98.0 on connectivity, 97.2 on shortest path and 91.7 on node degree. The best prompting results (ZERO-SHOT, COT, COT-BAG) reach only 84.9, 40.4 and 29.2 on these tasks.
  • GNNs do better on node degree and cycle check in low-sample regimes, which the authors attribute to their local inductive bias. GraphQA's random graphs also tend to contain only short cycles, so they do not resemble the hard worst-case instances.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 worksComputer Vision and Pattern Recognition · 3,621 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,948 works

Cite

Cite as Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi and Vahab Mirrokni. 2024. Understanding Transformer Reasoning Capabilities via Graph Algorithms. arXiv:2405.18512.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2405.18512 · arXiv 2405.18512

@misc{sanford2024understanding,
  title = {{Understanding Transformer Reasoning Capabilities via Graph Algorithms}},
  author = {Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi and Vahab Mirrokni},
  year = {2024},
  doi = {10.48550/arxiv.2405.18512},
  eprint = {2405.18512},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2405.18512}
}

References

91 references, 31 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Nicholas Schiefer, Sandeep Silwal, and Tal Wagner. Exponentially improving the complexity of simulating the weisfeiler-lehman test with graph neural networks, 2022. Cited on page 3. find
  2. Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. GPT-4 technical report. arXiv preprint arXiv:2303.08774, 2023. Cited on page 1.
  3. Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel graph connectivity in log diameter rounds. In FOCS, October 2018. Cited on pages 17 and 18. find
  4. Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al. Palm 2 technical report. arXiv preprint arXiv:2305.10403, 2023. Cited on page 41.
  5. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In ICLR, 2014. Cited on page 1.
  6. Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261, 2018. Cited on page…
  7. Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. JACM, 64(6), oct 2017. Cited on page 19. find
  8. James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. JMLR, 13(2), 2012. Cited on page 41. find
  9. Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of thoughts: Solving elaborate problems with large language models. AAAI, 38(16):17682–17690, March 2024. Cit… find
  10. Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Slobodan Mitrović, and Ronitt Rubinfeld. Massively parallel algorithms for small subgraph counting, 2022. Cited on pages 6 and 19. find
  11. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. NeurIPS, 2020. Cited on pages 1 and 41.
  12. Quentin Cappart, Didier Chételat, Elias B Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. JMLR, 24 (130):1–61, 2023. Cited on page 1. find
  13. Ziwei Chai, Tianjie Zhang, Liang Wu, Kaiqiao Han, Xiaohai Hu, Xuanwen Huang, and Yang Yang. GraphLLM: Boosting graph reasoning ability of large language model, 2023. Cited on page 3. find
  14. Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning on graphs: A model and comprehensive taxonomy. JMLR, 23(89):1–64, 2022. Cited on page 1. find
  15. Sam Coy and Artur Czumaj. Deterministic massively parallel connectivity. In STOC, STOC ’22, June 2022. Cited on page 19. find
  16. Antonia Creswell, Murray Shanahan, and Irina Higgins. Selection-inference: Exploiting large language models for interpretable logical reasoning. In ICLR, 2023. Cited on page 1. find
  17. Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. In OSDI’04: Sixth Symposium on Operating System Design and Implementation, pages 137– 150, San Francisco, CA, 2004. Cited on page 18. find
  18. Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018. Cited on page 1.
  19. Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR, 2021. Cited on page 1.
  20. Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020. Cited on page 3. — [arXiv:2012.09699](https://arxiv.org/abs/2012.09699) find
  21. Paul Erdős and Alfred Rényi. On random graphs. Publicationes Mathematicae Debrecen, 6: 290–297, 1959. Cited on page 40. find
  22. Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. In ICLR, 2024. Cited on pages 3, 6, 9, 40, 41, and 42.
  23. Fabian Frei and Koichi Wada. Efficient circuit simulation in mapreduce. abs/1907.01624, 2019. Cited on page 19. ArXiv, — [arXiv:1907.01624](https://arxiv.org/abs/1907.01624) find
  24. Roy Frostig, Matthew James Johnson, and Chris Leary. Compiling machine learning programs via high-level tracing. Systems for Machine Learning, 4(9), 2018. Cited on page 41. find
  25. Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. Conditional hardness results for massively parallel computation from distributed lower bounds. In FOCS, 2019. Cited on page 19. find
  26. Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, 2017. Cited on pages 1, 7, 8, 41, and 42.
  27. Sachin Goyal, Ziwei Ji, Ankit Singh Rawat, Aditya Krishna Menon, Sanjiv Kumar, and Vaishnavh Nagarajan. Think before you speak: Training language models with pause tokens. In ICLR, 2024. Cited on pages 2, 3, and 15. find
  28. Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint arXiv:1410.5401, 2014. Cited on page 1. find
  29. Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. TACL, 10:800–810, 2022. Cited on page 3.
  30. Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimal large language models. arXiv preprint arXiv:2203.15556, 2022. Cited on page 1.
  31. Bowen Jin, Gang Liu, Chi Han, Meng Jiang, Heng Ji, and Jiawei Han. Large language models on graphs: A comprehensive survey. arXiv preprint arXiv:2312.02783, 2023. Cited on page 3. find
  32. Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. NIPS, 2015. Cited on page 1. find
  33. Norman P. Jouppi, Cliff Young, Nishant Patil, David Patterson, Gaurav Agrawal, Raminder Bajwa, Sarah Bates, Suresh Bhatia, Nan Boden, Al Borchers, Rick Boyle, Pierre-luc Cantin, Clifford Chao, Chris Clark, Jeremy Coriell, Mike Daley, Matt Dau, Jeffrey Dean, Ben Gelb, Tara Vazir Ghaemmaghami, Rajendr… — In-Datacenter Performance Analysis of a Tensor Processing Unit
  34. John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Žídek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583–589, 2021. Cited on page 1.
  35. Lukasz Kaiser and Ilya Sutskever. Neural GPUs learn algorithms. In ICLR, 2016. Cited on page 1. find
  36. Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.08361, 2020. Cited on page 1.
  37. Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A Model of Computation for MapReduce, pages 938–948. Cited on pages 4, 17, and 18. find
  38. Nora Kassner, Oyvind Tafjord, Ashish Sabharwal, Kyle Richardson, Hinrich Schuetze, and Peter Clark. Language models with rationality. In Houda Bouamor, Juan Pino, and Kalika Bali, editors, EMNLP, December 2023. Cited on page 1. find
  39. Mehran Kazemi, Najoung Kim, Deepti Bhatia, Xin Xu, and Deepak Ramachandran. LAM-BADA: Backward chaining for automated reasoning in natural language. In ACL, 2023. Cited on page 1. find
  40. Jinwoo Kim, Tien Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners, 2022. Cited on pages 2, 3, and 31. find
  41. Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014. Cited on page 41.
  42. Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016. Cited on pages 1, 7, 8, 41, and 42.
  43. Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. NeurIPS, 35:22199–22213, 2022. Cited on page 41.
  44. Nayoung Lee, Kartik Sreenivasan, Jason D Lee, Kangwook Lee, and Dimitris Papailiopoulos. Teaching arithmetic to small transformers. In ICLR, 2024. Cited on pages 1 and 3.
  45. Yuxuan Li and James L. McClelland. Systematic generalization and emergent structures in transformers trained on structured tasks, 2022. Cited on page 3. find
  46. Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata, 2022. Cited on page 3. find
  47. Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In CVPR, 2021. Cited on page 1.
  48. Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint arXiv:1711.05101, 2017. Cited on page 41. find
  49. Andreas Loukas. What graph neural networks cannot learn: depth vs width. In ICLR, 2020. Cited on pages 1, 3, and 39. find
  50. Eran Malach. Auto-regressive next-token predictors are universal learners, 2023. Cited on page 2. find
  51. Amil Merchant, Simon Batzner, Samuel S Schoenholz, Muratahan Aykol, Gowoon Cheon, and Ekin Dogus Cubuk. Scaling deep learning for materials discovery. Nature, 624(7990):80–85, 2023. Cited on page 1. find
  52. William Merrill and Ashish Sabharwal. A logic for expressing log-precision transformers, 2022. Cited on page 2. find
  53. William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. TACL, 11:531–545, 2023. Cited on pages 2 and 32. find
  54. William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought, 2023. Cited on pages 2 and 6. find
  55. William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated transformers are constant-depth threshold circuits, 2021. Cited on pages 2 and 6. find
  56. Erxue Min, Runfa Chen, Yatao Bian, Tingyang Xu, Kangfei Zhao, Wenbing Huang, Peilin Zhao, Junzhou Huang, Sophia Ananiadou, and Yu Rong. Transformer for graphs: An overview from architecture perspective, 2022. Cited on page 3. find
  57. Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and Leman go machine learning: The story so far. JMLR, 24(1):15865–15923, 2023. Cited on pages 3 and 39. find
  58. Danupon Nanongkai and Michele Scquizzato. Equivalence classes and conditional hardness in massively parallel computations. Distributed Computing, 35(2):165–183, January 2022. Cited on pages 5, 17, 18, 19, and 20. find
  59. Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114, 2021. Cited on page 2.
  60. Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing complete. J. Mach. Learn. Res., 22(1), jan 2021. ISSN 1532-4435. Cited on pages 2 and 3. find
  61. Bryan Perozzi, Bahare Fatemi, Dustin Zelle, Anton Tsitsulin, Mehran Kazemi, Rami Al-Rfou, and Jonathan Halcrow. Let your graph do the talking: Encoding structured data for LLMs, 2024. Cited on pages 3, 41, and 42. find
  62. Jackson Petty, Sjoerd van Steenkiste, Ishita Dasgupta, Fei Sha, Dan Garrette, and Tal Linzen. The impact of depth and width on transformer language model generalization. NAACL, 2024. Cited on page 1. find
  63. Jacob Pfau, William Merrill, and Samuel R Bowman. Let’s think dot by dot: Hidden computation in transformer language models. arXiv preprint arXiv:2404.15758, 2024. Cited on pages 2 and 15. find
  64. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. JMLR, 21(1):5485–5551, 2020. Cited on pages 1, 6, and 41.
  65. Machel Reid, Nikolay Savinov, Denis Teplyashin, Dmitry Lepikhin, Timothy Lillicrap, Jean-baptiste Alayrac, Radu Soricut, Angeliki Lazaridou, Orhan Firat, Julian Schrittwieser, et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv preprint arXiv:2403.05530,…
  66. Yu Rong, Yatao Bian, Tingyang Xu, Weiyang Xie, Ying Wei, Wenbing Huang, and Junzhou Huang. Self-supervised graph transformer on large-scale molecular data. NeurIPS, 33, 2020. Cited on page 3. find
  67. Tim Roughgarden, Sergei Vassilvitskii, and Joshua R. Wang. Shuffles and circuits (on lower bounds for modern parallel computation). J. ACM, 65(6), nov 2018. Cited on page 19. find
  68. Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers, 2023. Cited on pages 3, 31, 32, 35, and 36. find
  69. Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic depth, 2024. Cited on pages 2, 3, 4, 5, 6, 15, 18, 20, 21, 22, 30, 31, 32, and 39. find
  70. Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61–80, 2008. Cited on page 1. find
  71. Noam Shazeer. GLU variants improve transformer. arXiv preprint arXiv:2002.05202, 2020. Cited on page 41. find
  72. Kaya Stechly, Matthew Marquez, and Subbarao Kambhampati. GPT-4 doesn’t know it’s wrong: An analysis of iterative prompting for reasoning problems, 2023. Cited on page 3. find
  73. Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805, 2023. Cited on page 1.
  74. Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288, 2023. Cited on page 1.
  75. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NeurIPS, 2017. Cited on pages 1, 15, and 41.
  76. Petar Veličković and Charles Blundell. Neural algorithmic reasoning. Patterns, 2(7), 2021. Cited on page 1. find
  77. Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell. The CLRS algorithmic reasoning benchmark. In ICML, 2022. Cited on page 1. find
  78. Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? In NeurIPS, 2023. Cited on pages 3 and 41.
  79. Colin Wei, Yining Chen, and Tengyu Ma. Statistically meaningful approximation: a case study on approximating turing machines with transformers, 2021. Cited on page 2. find
  80. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. NeurIPS, 2022. Cited on pages 1, 2, 15, and 41.
  81. Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. nti, Series, 2(9):12–16, 1968. Cited on pages 3 and 39. find
  82. Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?, 2018. Cited on pages 1, 3, 7, 8, 39, 41, and 42.
  83. Andrew Chi-Chih Yao. Some complexity questions related to distributive computing(preliminary report). In STOC, page 209–213, New York, NY, USA, 1979. Cited on page 36. find
  84. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. NeurIPS, 2024. Cited on page 1. find
  85. Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, and Yongfeng Zhang. Language is all a graph needs, 2023. Cited on page 3. find
  86. Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions?, 2019. Cited on page 2.
  87. Wojciech Zaremba and Ilya Sutskever. Learning to execute. In ICLR, 2015. Cited on page 1. find
  88. Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of GNNs via graph biconnectivity. In ICLR, 2023. Cited on pages 1 and 3. find
  89. Yi Zhang, Arturs Backurs, Sébastien Bubeck, Ronen Eldan, Suriya Gunasekar, and Tal Wagner. Unveiling transformers with lego: a synthetic reasoning task, 2022. Cited on page 3. find
  90. Hattie Zhou, Azade Nova, Hugo Larochelle, Aaron Courville, Behnam Neyshabur, and Hanie Sedghi. Teaching algorithmic reasoning via in-context learning. arXiv preprint arXiv:2211.09066, 2022. Cited on page 1.
  91. Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Josh Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms can transformers learn? a study in length generalization. In ICLR, 2024. Cited on page 1.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sanford-2024-understanding-transformer-reasoning-capabilities-graph/