Transformers, parallel computation, and logarithmic depth

2024/02/14 by Sanford, Clayton, Hsu, Daniel, Telgarsky, Matus · 7 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.2402.09268

Abstract

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.

Cited by

• Optimality and NP-Hardness of Transformers in Learning Markovian Dynamical Functions
• Toward Mechanistic Explanation of Deductive Reasoning in Language Models
• Allocation of Parameters in Transformers
• Limit Analysis for Symbolic Multi-step Reasoning Tasks with Information Propagation Rules Based on Transformers
• A Formal Comparison Between Chain-of-Thought and Latent Thought
• Fast attention mechanisms: a tale of parallelism
• Beyond Memorization: Extending Reasoning Depth with Recurrence, Memory and Test-Time Compute Scaling

Related

• The Parallelism Tradeoff: Limitations of Log-Precision Transformers
• Sub-Linear Memory: How to Make Performers SLiM
• Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuits
• Saturated Transformers are Constant-Depth Threshold Circuits
• Exact Expressive Power of Transformers with Padding