The Parallelism Tradeoff: Limitations of Log-Precision Transformers

William Merrill, Ashish Sabharwal

Despite their omnipresence in modern NLP, characterizing the computational power of transformer neural nets remains an interesting open question. We prove that transformers whose a…