Transformers, parallel computation, and logarithmic depth

Clayton Sanford, Daniel Hsu, Matus Telgarsky
2/14/2024
cs.LG

No official code found. Best implementation: chsanford/hop-induction-heads (12 stars, last commit 2024-02-15).

Abstract

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.

View on arXivView PDF

Code Implementations(1)

chsanford/hop-induction-headsCommunity100%

A code repository accompanying the paper "Transformers, parallel computation, and logarithmic depth" by Clayton Sanford, Daniel Hsu, and Matus Telgarsky.

122Python, Jupyter NotebookFeb 12, 20242 years ago

Similar Papers

Universal Approximation Theorem for a Single-Layer Transformer

84% match2025

A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers

84% match2025

Fast attention mechanisms: a tale of parallelism

84% match2025

Are Transformers with One Layer Self-Attention Using Low-Rank Weight Matrices Universal Approximators?

83% match2023

Layer-Parallel Training for Transformers

83% match2026

Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions

83% match2023

Cite this paper

@article{sanford2024transformers,
  title  = {Transformers, parallel computation, and logarithmic depth},
  author = {Clayton Sanford and Daniel Hsu and Matus Telgarsky},
  year   = {2024},
  eprint = {2402.09268},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2402.09268v1},
  journal = {ICML 2024 2024}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2402.09268.svg)](https://codeofpaper.com/paper/2402.09268)

Discussion