45 min
Seminar, Hosted by Simons Institute for the Theory of Computing
The Parallelism Tradeoff: Understanding Transformer Expressivity Through Circuit Complexity
New York University
Recording
Abstract
The speaker uses circuit complexity to characterize transformers operating at logarithmic arithmetic precision. A simulation by uniform, constant-depth threshold circuits gives conditional limits on solving linear equalities and recognizing certain grammars. The talk asks whether the parallelism that enables large-scale training also imposes computational limitations.
Topics
- transformers
- Circuit Complexity, broader topic: complexity
- logarithmic arithmetic precision, broader topic: precision
- uniform, constant-depth threshold circuits, broader topic: circuits
- linear equalities, search World Wide
- grammars, search World Wide
- parallelism
- large-scale training, broader topic: training
- computational limitations
- expressivity