Transformers, parallel computation, and logarithmic depth
<|reference_start|>Transformers, parallel computation, and logarithmic depth: We show that a constant number of self-attention layers can efficiently simulate, and be simulated by, a constant number of communication rounds of Massively Parallel Computation. As a consequence, we show that logarithmic depth is sufficient for transformers to solve basic computational tasks that cannot be efficiently solved by several other neural sequence models and sub-quadratic transformer approximations. We thus establish parallelism as a key distinguishing property of transformers.<|reference_end|>
@article{sanford2024transformers,,
    title={Transformers, parallel computation, and logarithmic depth},
    author={Clayton Sanford, Daniel Hsu, Matus Telgarsky},
    journal={arXiv preprint arXiv:2402.09268},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.09268},
    primaryClass={cs.LG}
}