Lower bounds for one-layer transformers that compute parity
Provides theoretical limitations on the expressiveness of one-layer transformers for a fundamental function, relevant to understanding their computational power.
This note proves that one-layer transformers cannot compute the parity function unless the product of the number of heads and the degree of the post-processing function grows linearly with input length, extending the result to ReLU networks with a margin-dependent bound.
This note shows that no self-attention layer post-processed by a rational function can sign-represent the parity function unless the product of the number of heads and the degree of the post-processing function grows linearly with the input length. Combining this lower bound with rational approximation of ReLU networks yields a margin-dependent extension for self-attention layers post-processed by ReLU networks.