Theoretical limitations of multi-layer Transformer

Transformers, especially the decoder-only variants, are the backbone of most modern large language models. Yet, we have a very limited understanding of their limitations (i.e., what tasks they cannot solve) besides the simplest 1-layer case. Due to the difficulty of analyzing multi-layer models, all previous work relies on unproven complexity conjectures to show limitations for multi-layer Transformers. In this work, we prove the first unconditional lower bound against multilayer decoder-only transformers. For any constant L, we prove that any L-layer decoder-only transformer needs a polynomial model dimension $\left(n^{\Omega(1)}\right)$ to perform sequential composition of L functions over an input of n tokens. As a consequence, our results give: (1) the first depthwidth trade-off for multi-layer transformers, exhibiting that the L-step composition task is exponentially harder for L-layer models compared to $(L+1)$-layer ones; (2) an unconditional separation between encoder and decoder, exhibiting a hard task for decoders that can be solved by an exponentially shallower and smaller encoder; (3) a provable advantage of chain-of-thought, exhibiting a task that becomes exponentially easier when the model is allowed to produce an intermediate sequence of tokens before outputting the final answer. On the technical side, we propose the multi-party autoregressive communication model that abstracts the key aspects of a decoder-only Transformer. In particular, lower bounds within this communication model imply lower bounds against decoder-only transformers, independent of their implementation details. To prove lower bounds in this communication model, we also introduce a new proof technique that finds a certain indistinguishable decomposition of all possible inputs iteratively. We believe our new communication model and proof techniques will be helpful to understand the computational power of transformers further.