2026-09-21
Constant attention layers simulate constant-round MPC. Log-depth transformers solve connectivity and k-hop; RNNs, Mamba, and sparse attention need linear depth at similar width.
Most theory on what transformers can compute sits at two poles. Universality results say a large enough net can approximate any sequence map or even a Turing machine, but the size blows up with the task, so they do not explain why transformers beat RNNs. Fine-grained lower bounds for constant depth say the opposite: with fixed layers and growing context, parenthesis matching, Boolean formula evaluation, and graph connectivity are all out of reach. Production models live in the middle, where context N grows fast and depth L and width m stay sublinear in N.
This ICML 2024 paper pins that middle regime to distributed computing. Clayton Sanford and Daniel Hsu at Columbia, with Matus Telgarsky at NYU, show that a constant number of self-attention layers can simulate, and be simulated by, a constant number of rounds of Massively Parallel Computation (MPC): a MapReduce-style model where each machine holds sublinear memory and communication happens in synchronized rounds. Parallelism is the property that separates transformers from RNNs, GNNs, and sparse-attention variants.
The technical core is a two-way simulation. Query, key, and value maps, and the MLPs, are arbitrary per-position functions; the only restriction is how positions interact. Indices can be written into embeddings, so the theorems do not need a separate positional encoding. Intermediate values use p = Θ(log N) bits, in line with low-precision training.
Forward direction: any R-round (γ, δ)-MPC protocol with per-machine memory s = O(N^δ), δ < 1, is implemented by a transformer of depth L = R+1, embedding size m = O(N^{4δ} log N), and H = O(log log N) heads. Local computation on each machine is folded into per-position MLPs and Q/K/V maps. The hard step is routing up to s addressed messages at once. One attention layer does the routing: messages are packed with sparse redundancy, a single head runs sparse propagation (N subset-averages in parallel), and error correction recovers the originals from those averages. The construction uses all-pairs attention; the paper notes that a subquadratic stand-in may not exist. When δ ≥ 1/4 the embedding already has size on the order of N, so a single layer can swallow the whole input and depth stops mattering. The interesting regime is strongly sublinear memory.
Backward direction: a depth-L transformer with mH = O(N^δ) is simulated by an O(L/(δ′−δ))-round MPC protocol on O(N²) machines. Three machine types split the work: one token machine per position for Q/K/V, one inner-product machine per token pair, and a set of propagation machines for the softmax aggregate.
The companion toy task is k-hop induction heads. A standard induction head looks up the token that followed the previous occurrence of the current token; k-hop chases that pointer k times. It looks serial. A pointer-doubling circuit solves it anyway: two layers build a 1-hop (copy the previous token, then lastOccurrence), and each later layer doubles the hop length. Depth L = ⌊log₂ k⌋+2, constant width, and a single causal head suffice.
Graph algorithms come for free from the MPC literature. For graphs whose components have diameter at most D, some transformer with m = O(N^ε), H = O(log log N), and L = O(log D) labels connected components; spanning forest and related problems transfer the same way. Under the standard conjecture that telling a single N-cycle from two N/2-cycles takes Ω(log N) sublinear-memory MPC rounds, any transformer with mH = O(D^{1-ε}) needs depth Ω(log D). Log depth is close to tight.
The GNN contrast is sharp. Loukas's CONGEST bound: there exist N-edge graphs where a message-passing GNN needs L√m = Ω̃(N^{1/4}) to decide subgraph connectivity or spanning-tree-ness. Transformers are not stuck sending messages along the input edges. They can rewire every layer, so log depth is enough.
The k-hop lower bound is conditional on the same conjecture: for k = Θ(N^ξ) and mH = O(k^{1-ε}), depth is Ω(log k). Training GPT-2-style causal transformers from HuggingFace with Adam for 10^5 steps (learning rate 10^{-4}, batch 32), N = 100, alphabet size 4, k up to 16, and fresh samples every step, yields an exponential depth-versus-k curve at 4 heads and width 128:
| Depth L | k with low error | Parameters |
| 2 | about k=1; other tasks ≥10% error | 413k |
| 3 | k≤2 at ≤1% error | 612k |
| 4 | about k≤4 | 810k |
| 5 | about k≤8 | 1.01M |
| 6 | k≤16; 6.2% error at k=16 | 1.21M |
The threshold sits at ⌊log₂ k⌋+2, matching the construction. Doubling to 8 heads and width 256 is roughly as helpful as adding one layer, and costs more parameters. Learned attention is nearly hard selection: layer 1 aligns to the predecessor; later layers align to find¹, find², find³, find⁸, the same doubling circuit. With 3000 finite samples the error curve already tracks the infinite-sample run; 1000 samples overfit, but a 6-layer net still beats a 4-layer net on hop3 by stacking several 1-hops rather than doubling.
RNNs, and Mamba at inference, need either depth at least k or width m = Ω(N/k^6). Kernel approximations such as Performer need a feature dimension near N. Longformer needs a window or global-token rate dense enough to erase the subquadratic gain. A 1-layer model with chain-of-thought needs at least k extra tokens, or the same width lower bound.
This is a proof-level answer to why full attention and non-trivial depth are not optional. Constant depth is close to AC^0 in circuit complexity and cannot do connectivity; log depth is exactly the MPC threshold for that problem. Replacing full attention with a linear-time state-space model or sparse attention turns a logarithmic-depth algorithm into a linear-depth one on pointer-chasing and global aggregation tasks.
It is an expressivity paper, not a new architecture, and it does not yield a training recipe. Two design takeaways still stand. The communication pattern of all-pairs attention may be load-bearing. Depth buys exponential composition capacity that width does not replace cheaply.
Every lower bound sits on the one-versus-two cycle conjecture; none is unconditional. The forward simulation inflates embedding size to O(s^4 log N). Follow-up work by Sanford et al. in 2024 relaxes the memory condition to any strictly sublinear local memory, so the compilation overhead here is real. MLPs and Q/K/V maps are arbitrary per-position functions: the theorems describe information flow, not a guarantee that a standard transformer with a fixed-width MLP will learn the same circuit.
The experiments are tiny: N=100, a 4-symbol alphabet, at most 6 layers, about 4.8M parameters, run on an M1 laptop. Width 128 already exceeds context 100, so shallow models can dump logic into the MLP; the paper flags this. k-hop is synthetic; transfer to natural language is untested. Learnability is open: the theory constructs a circuit, training only shows that Adam can find a similar one. MPC also says nothing about GPU training or inference throughput.