New Lower Bound Techniques for Transformers

Existing lower bound techniques for transformers still do not allow us to fully understand even the one-layer case. One example of this is such a fundamental and simple task like PARITY – checking if the number of 1s in a binary input sequence is even. While a 2-layer construction for PARITY due to Chiang and Cholak is known, it is open if 1-layer transformers can solve PARITY. Known techniques like communication complexity and split vc dimension are not enough to resolve this problem as in the case of PARITY they do not yield non-trivial lower bounds. In this paper, we develop a new technique that allows us to resolve this problem. We first show for every language, computable by a 1-layer transformer, can be in some sense expressed in the first-order theory of reals with addition, multiplication and order. More precisely, one can write a fixed formula $\Phi$ where, for each input length, free variables can be substituted by linear expressions in input bits in a way that the resulting formula computes the restriction of the language to this input length. Using results from Boolean function complexity, we then conclude that every language 1-layer transformers can do has average sensitivity $O(\sqrt{n}\cdot \mathrm{polylog}(n))$, which means that PARITY is not doable by 1-layer transformers. Moreover, we notice that for 1-layer transformers with a single attention head, the formula $\Phi$ does not require multiplication, and this allows us to separate 1-layer transformers with 1 head from 1-layer transformers with 2 heads. More specifically, we show that the problem of checking, whether a sequence of bits is ordered, is not doable by 1-head 1-layer transformers but is doable by a 2-head 1-layer transformer. A similar separation result was previously obtained for the attention-only model, while our results assume the model with the output MLP.