Transformers, parallel computation, and logarithmic depth
Open accessAbstract
We show that a constant number of self-attention layers can efficiently simulate, and be simulated by, a constant number of communication rounds of Massively Parallel Computation. As a consequence, we show that logarithmic depth is sufficient for transformers to solve basic computational tasks that cannot be efficiently solved by several other neural sequence models and sub-quadratic transformer approximations. We thus establish parallelism as a key distinguishing property of transformers.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The Transformer design has limited computational depth, as stated in recent studies on state-tracking and similar computational capabilities of models.
“This design, however, has limited computational depth as also stated in recent studies on state-tracking and similar computational capabilities of models (Merrill et al. 2024; Sanford et al. 2024; Grazzi et al. 2025).”
From Nested Learning: The Illusion of Deep Learning Architectures (2025) · cites this paper as Sanford et al. 2024
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
The publisher hasn’t deposited this paper’s reference list.
Research works printed but not linked: 34
- Alekh Agarwal, Olivier Chapelle, Miroslav Dudík, and John Langford. A reliable effective terascale linear learning system. Journal of Machine Learning Research, 15(1):1111-1133, 2014.
- Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev. Parallel algorithms for geometric graph problems. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, pages 574-583, 2014.
- Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, and Peilin Zhong. Parallel graph connectivity in log diameter rounds. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, October 2018. doi: 10.1109/focs.2018.00070. URL http://dx.doi.org/10.1109/FOCS.2018.00070. · DOI
- Sepehr Assadi and Vishvajeet N. Graph streaming lower bounds for parameter estimation and property testing via a streaming xor lemma. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC '21. ACM, June 2021. doi: 10.1145/3406325.3451110. URL http: //dx.doi.org/10.1145/3406325.3451110. · DOI
- Paul Beame, Paraschos Koutris, and Dan Suciu. Communication steps for parallel query processing. Journal of the ACM (JACM), 64(6):1-58, 2017.
- Soheil Behnezhad, Sebastian Brandt, Mahsa Derakhshan, Manuela Fischer, MohammadTaghi Hajiaghayi, Richard M Karp, and Jara Uitto. Massively parallel computation of matching and mis in sparse graphs. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 481-490, 2019.
- Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the ability and limitations of transformers to recognize formal languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, 2020.
- Junyoung Chung, Caglar Gulcehre, KyungHyun Cho, and Yoshua Bengio. Empirical evaluation of gated recurrent neural networks on sequence modeling. arXiv preprint arXiv:1412.3555, 2014. · arXiv
- Kevin Clark, Urvashi Khandelwal, Omer Levy, and Christopher D Manning. What does bert look at? an analysis of bert's attention. arXiv preprint arXiv:1906.04341, 2019. · arXiv
- Sam Coy and Artur Czumaj. Deterministic massively parallel connectivity. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, page 162-175, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450392648. doi: 10.1145/3519935.3520055. URL https://doi.org/10.1145/3519935.3520055. · DOI
- Amit Daniely. Depth separation for neural networks. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pages 690-696. PMLR, 07-10 Jul 2017. URL https://proceedings.mlr.press/v65/daniely17a.html.
- Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory- efficient exact attention with io-awareness. In NeurIPS, 2022.
- Jeffrey Dean and Sanjay Ghemawat. Mapreduce: Simplified data processing on large clusters. In OSDI, pages 137-150, 2004.
- Tim Dettmers, Mike Lewis, Younes Belkada, and Luke Zettlemoyer. Llm.int8(): 8-bit matrix multiplication for transformers at scale. In Advances in Neural Information Processing Systems, volume 35, 2022.
- Pavol Duris, Zvi Galil, and Georg Schnitger. Lower bounds on communication complexity. In Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, page 81-91, 1984.
- Ronen Eldan and Ohad Shamir. The power of depth for feedforward neural networks. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 907-940, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL https://proceedings.mlr.press/v49/eldan16.html.
- Mohsen Ghaffari, Fabian Kuhn, and Jara Uitto. Conditional hardness results for massively parallel computation from distributed lower bounds. In IEEE 60th Annual Symposium on Foundations of Computer Science, pages 1650-1663, 11 2019. doi: 10.1109/FOCS.2019.00097. · DOI
- Michael T Goodrich, Nodari Sitchinava, and Qin Zhang. Sorting, searching, and simulation in the mapreduce framework. In International Symposium on Algorithms and Computation, pages 374-383. Springer, 2011.
- Yiding Hao, Dana Angluin, and Robert Frank. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Trans. Assoc. Comput. Linguistics, 10:800-810, 2022. URL https: //transacl.org/ojs/index.php/tacl/article/view/3765.
- Sungjin Im, Ravi Kumar, Silvio Lattanzi, Benjamin Moseley, Sergei Vassilvitskii, et al. Massively parallel computation: Algorithms and applications. Foundations and Trends® in Optimization, 5(4):340-417, 2023.
- 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.
- Howard Karloff, Siddharth Suri, and Sergei Vassilvitskii. A model of computation for mapreduce. In Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, pages 938-948, 12 2010. doi: 10.1137/ 1.9781611973075. · DOI
- Valerii Likhosherstov, Krzysztof Choromanski, and Adrian Weller. On the expressive power of self-attention matrices. arXiv preprint arXiv:2106.03764, 2021. · arXiv
- Andreas Loukas. What graph neural networks cannot learn: depth vs width. arXiv preprint arXiv:1907.03199, 2019. · arXiv
- Noam Nisan and Avi Wigderson. Rounds in communication complexity revisited. SIAM Journal on Computing, 22(1):211-219, 1993. doi: 10.1137/0222016. URL https://doi.org/10.1137/0222016. · DOI
- Christos H. Papadimitriou and Michael Sipser. Communication complexity. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, page 196-200, 1982.
- Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing complete. Journal of Machine Learning Research, 22(1):3463-3497, 2021.
- Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9, 2019.
- Anna Rogers, Olga Kovaleva, and Anna Rumshisky. A primer in bertology: What we know about how bert works. Transactions of the Association for Computational Linguistics, 8:842-866, 2021.
- Tim Roughgarden, Sergei Vassilvitskii, and Joshua Wang. Shuffles and circuits (on lower bounds for modern parallel computation). Journal of the ACM, 65:1-24, 11 2018. doi: 10.1145/3232536. · DOI
- Matus Telgarsky. Benefits of depth in neural networks. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1517-1539, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMLR. URL https://proceedings.mlr.press/v49/telgarsky16.html.
- Mehmet Ozgur Turkoglu, Stefano D'Aronco, Jan Dirk Wegner, and Konrad Schindler. Gating revisited: Deep multi-layer rnns that can be trained. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44 (8):4081-4092, 2021.
- Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems 30, 2017.
- Ziwei Wang, Changyuan Wang, Xiuwei Xu, Jie Zhou, and Jiwen Lu. Quantformer: Learning extremely low-precision vision transformers. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Cited by
Sorted by citations
Chen, P., Xu, B., He, W., & Zhang, X. (2025) · Process Safety and Environmental Protection · doi:10.1016/j.psep.2025.107804 · Cited by 11 · see citing works
Scalable and accurate online multivariate anomaly detection
Salles, R. P., Lange, B., Akbarinia, R., Masséglia, F., Ogasawara, E., & Pacitti, E. (2025) · Information Systems · doi:10.1016/j.is.2025.102524 · Cited by 5 · see citing works
Nested Learning: The Illusion of Deep Learning Architectures
Behrouz, A., Razaviyayn, M., Zhong, P., & Mirrokni, V. (2025) · arXiv · doi:10.48550/arxiv.2512.24695 · Cited by 1 · see citing works
“…expressive power of the models in multiple aspects, for example: (i) The computational depth of deep models might not change with more layers [21, 22], leaving their ability to implement complex algorithms untouched compared to traditional shallow approaches [23]; (ii) The capacity of some class…”
- Authors
- Sanford, C., Hsu, D., & Telgarsky, M.
- Affiliations
- Columbia University (US)
- New York University (US)
- ORCID
- Hsu, Daniel
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2024
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2402.09268
- OpenAlex
- W4391871302
- Cited by
- 2
- References
- 0
- Citations by year
- 2025: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- Locations
- arXiv (Cornell University) (submittedVersion, cc-by)
- arXiv (Cornell University) (cc-by)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- transformer models, self-attention, massively parallel computing, communication rounds, parallelism, computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
