Reproduce “Transformers, parallel computation, and logarithmic depth” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Clayton Sanford, Daniel Hsu, Matus Telgarsky
This work by Sanford, Hsu, and Telgarsky establishes a formal connection between transformers and the Massively Parallel Computation (MPC) model, identifying parallelism as a core computational primitive that distinguishes transformers. The authors demonstrate that transformers can solve the k-hop pointer chasing task in O(log k) depth, leveraging multi-layer attention to perform parallel lookups, with empirical results confirming this logarithmic scaling and mechanistic analyses revealing the implementation of pointer-doubling algorithms.
Key insights
- Transformers' multi-layer self-attention mechanism naturally supports massively parallel computation, a distinguishing feature from other neural architectures.
- The Massively Parallel Computation (MPC) model from distributed computing theory provides a formal framework for analyzing transformers' computational power.
- Transformers can solve certain seemingly sequential tasks, such as k-hop pointer chasing, with logarithmic depth by implementing parallel algorithms like pointer doubling.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.