Investigating whether transformer architectures can solve computational problems beyond the reach of constant-depth circuits, bridging circuit complexity theory and modern deep learning.
We investigate the computational power of transformer architectures through the lens of circuit complexity. Specifically, we ask: can transformers solve problems that require super-constant depth in traditional circuit models?
This question sits at the intersection of classical complexity theory and modern machine learning, offering insights into the fundamental capabilities and limitations of attention-based architectures.
We show that even simple transformer architectures can implement functions that provably require logarithmic depth in standard circuit models. This separation reveals an inherent advantage of the transformer inductive bias.
Our results suggest that transformers possess a unique computational structure that goes beyond what traditional complexity-theoretic models would predict.