The Parallelism Tradeoff: Understanding Transformer Expressivity Through Circuit Complexity

Explore the computational power of transformer neural networks in this 45-minute lecture by Will Merrill from New York University. Delve into the proof that transformers with logarithmic arithmetic precision can be simulated by constant-depth logspace-uniform threshold circuits. Examine the implications of this finding on the limitations of transformers, such as their inability to solve certain problems if L≠P. Investigate the concept of a fundamental parallelism tradeoff, which suggests that highly parallelizable model architectures like transformers may have inherent weaknesses. Consider the potential implications of this tradeoff on the scaling paradigm in machine learning and natural language processing.