Transformers, parallel computation, and logarithmic depth

Clayton Sanford; Daniel Hsu; Matus Telgarsky

RECORD

Transformers, parallel computation, and logarithmic depth

Clayton Sanford, Daniel Hsu, Matus Telgarsky

Machine Learning · Submitted 14 Feb 2024

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim We thus establish parallelism as a key distinguishing property of transformers.

how it is stated · asserted 1.00 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 2,929 input tokens.

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.09 · human participants 0.02 · controlled comparison 0.12 · randomized assignment 0.01 · states quantitative result 0.66 · compares with prior results 0.85 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	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.	result 0.85	0.93	0.45	asserted 1.00
s1	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.	result 0.92	0.92	0.44	asserted 1.00
s2	We thus establish parallelism as a key distinguishing property of transformers.	interpretation 1.00	0.78	0.64	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 0.97.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original 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.

Human review

How Pith checks papers → · Full audit of this paper →

References

Forward citations

Cited by 9 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Attention-based representations for multi-task computation
cs.LG 2026-08 accept novelty 7.0 of 10

For min/max readout, two attention heads beat one head by an exponential resource gap, and for n-bit parity and symmetric Boolean functions, heads times polynomial degree must reach the threshold degree, with matching...
Scaling Latent Reasoning via Looped Language Models
cs.CL 2025-10 unverdicted novelty 7.0 of 10

Looped language models with latent iterative computation and entropy-regularized depth allocation achieve performance matching up to 12B standard LLMs through superior knowledge manipulation.
Is Random Attention Sufficient for Sequence Modeling? Disentangling Trainable Components in the Transformer
cs.LG 2025-06 conditional novelty 7.0 of 10

Freezing query and key attention weights still lets transformers form induction heads and stay close to standard performance on language modeling, while random static attention (MixiT) fails on in-context tasks but su...
Understanding the Skill Gap in Recurrent Language Models: The Role of the Gather-and-Aggregate Mechanism
cs.LG 2025-04 conditional novelty 7.0 of 10

In both Transformers and SSMs, in-context retrieval is performed by a small set of Gather and Aggregate heads, and the Transformer-SSM gap can be reduced to how well these few heads implement this mechanism.
SciDocBench: A Workflow-Centered Benchmark and Data Pipeline for Scientific Document Understanding
cs.AI 2026-09 conditional novelty 6.0 of 10

A new workflow-centered benchmark and data pipeline shows that current multimodal models score at most 62.6/100 on scientific document understanding, with the largest gaps in perception, extraction, and cross-document...

Show 4 more citing papers

Transformers Meet In-Context Learning: A Universal Approximation Theory
cs.LG 2025-06 accept novelty 6.0 of 10

A constructive theorem shows that transformers can perform in-context learning for any Barron-type function class by combining universal features with an emulated Lasso solver.
Attention Mechanism, Max-Affine Partition, and Universal Approximation
cs.LG 2025-04 conditional novelty 6.0 of 10

A single-head attention layer with a linear preprocessing layer is a universal approximator for continuous functions on compact domains, in both L∞ and Lp norms, for both self- and cross-attention.
Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limits
cs.CL 2025-05 conditional novelty 5.0 of 10

Matching token boundaries to the atomic units of a task, such as one letter per token, can improve LLM accuracy on symbolic reasoning by tens of percentage points and may matter more than model size.
A Theory for Compressibility of Graph Transformers for Transductive Learning
cs.LG 2024-11 conditional novelty 4.0 of 10

Under norm, low-rank, or clustering assumptions, a graph transformer's hidden dimension can be compressed with only small error in outputs and attention scores.

How the literature uses it

29 arXiv papers cite this in 53 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 28 sentences without a confident label

Compares with it 4 papers

The result follows from <Ref> and the construction for non-looped models from [ref] (restated in <Ref>).

Reasoning with Latent Thoughts: On the Power of Looped Transformers · Looped models can simulate non-looped models · 0.91
For $s = O(1)$ specifically, $⌈k/s ⌉= Θ(k)$ matches the serial upper bound, giving a tight $Θ(k)$ characterization in that sub-regime—comparable to RNNs (which are stuck at $Θ(k)$ under [ref] 's conditional lower bound requiring RNN width $O(N/k^6)$).

How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers · Product lower bound (conjectured) · 0.97
Compared with several existing multi-hop reasoning benchmarks [ref] , GAR is two-hop.

Benchmarking and Understanding Compositional Relational Reasoning of LLMs · Evaluating LLMs on GAR · 0.96

Cites it as support 3 papers

However, Transformers can only sequentially process $𝐡$ a fixed number of times [ref] , limited by their number of layers.

Counting Ability of Large Language Models and Impact of Tokenization · Inductive Counting and Computation · 0.97
To solve a given task, there is a theoretical lower bound on the required depth of computation [ref] .

Why Prompt Design Matters and Works: A Complexity Analysis of Prompt Search Space in LLMs · Nature of Inductive Reasoning · 0.97
Transformers, on the other hand, process all time steps in parallel, ensuring consistent computational efficiency regardless of sequence length [ref] .

Foundation Models for Time Series: A Survey · Scalability and Parallelism Advantages Over Traditional Architectures · 0.99

Cites it as background 12 papers

[ref] proved Transformer–MPC equivalence.

How Much Cache Does Reasoning Need? Depth-Cache Tradeoffs in KV-Compressed Transformers · Related Work · 0.91
The expressive power of neural sequence models has been an active area of research, targeting both RNNs and Transformers [ref] .

Separations in the Representational Capabilities of Transformers and Recurrent Architectures · Related Work · 1.00
One line of work studies compositional or multi-step reasoning [ref] .

Benchmarking and Understanding Compositional Relational Reasoning of LLMs · Introduction · 0.99

What it cites · 4 sentences without a confident label

Compares with 1 paper

By restating Corollary 4.2 of [ref] , we demonstrate a sharp contrast in the abilities of GNNs and transformers to solve graph algorithmic tasks.

What graph neural networks cannot learn: depth vs width · GNNs need polynomial depth for graph connectivity · 0.84

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.