Fast attention mechanisms: a tale of parallelism

Alexandr Andoni; Clayton Sanford; Daniel Hsu; Hantao Yu; Jingwen Liu

REVIEW 2 major objections 5 minor 1 cited by

This paper claims that a sub-quadratic attention mechanism called ANNA matches the expressive power of Massively Parallel Computation and simulates MPC with close to linear machine counts, closing the machine-count gap left by standard atte

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

ANNA, a hashing-based sub-quadratic attention mechanism, provably preserves standard attention's MPC expressiveness and can simulate low-rank attention, while being simulable by MPC with near-linear machines.

T0 review reviewed 2026-08-04 challenge →

load-bearing objection Real theoretical advance in efficient-attention expressivity, with a fixable-but-real gap in the ANNA definition around empty neighborhoods. the 2 major comments →

arxiv 2509.09001 v1 pith:FEIDO233 submitted 2025-09-10 cs.LG

Fast attention mechanisms: a tale of parallelism

Jingwen Liu , Hantao Yu , Clayton Sanford , Alexandr Andoni , Daniel Hsu This is my paper

classification cs.LG MSC 68T0768Q1068W15

keywords transformerattention mechanismMassively Parallel Computationlocality-sensitive hashingapproximate nearest neighborexpressive powerlow-rank attentionk-hop induction heads

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Standard attention matches the parallel-computing model MPC, but only by spending up to N² machines when simulating a transformer. This paper proposes ANNA, an attention mechanism that uses locality-sensitive hashing to let each token attend only to nearby keys, giving sub-quadratic runtime. It proves ANNA-transformers can simulate any sublinear-memory MPC algorithm with O(R) layers, and any ANNA-transformer can be simulated by an O(L)-round MPC protocol with near-linear machines. That tightens the correspondence enough to transfer MPC round lower bounds to efficient transformers, and it shows low-rank attention is no stronger than ANNA. The paper also gives explicit ANNA constructions for Match2 and k-hop reasoning tasks.

Core claim

The central claim is that ANNA-transformers and MPC are equivalent up to constant factors in depth/rounds and sublinear width/memory, with the MPC simulation using N^(1−δ+O(1/c²)) machines instead of N². The proof uses the fact that exact-match attention—the r=0, c→∞ limit of ANNA—can route messages between simulated machines by exact key equality, so every round of MPC becomes one attention layer. Conversely, the LSH implementation of ANNA can be realized in MPC by sorting/hashing keys and queries per table, and the hash-table count ℓ=Θ(N^{3ρ} log N) with LSH quality ρ<1/3 keeps total resources subquadratic. The same machinery yields constant/log-depth ANNA solutions to Match2 and k-hop and

What carries the argument

ANNA restricts each query's attention to keys that hash to the same bucket in ℓ locality-sensitive hash tables, averaging the associated values; its runtime O(mN^{1+3ρ}) is subquadratic when the LSH quality ρ satisfies ρ<1/3, which standard Euclidean LSH achieves with ρ=1/c²+o(1) for approximation factor c>√3. The proof isolates Exact-Match Attention, the r=0, c→∞ special case, to show that one ANNA layer can reroute all MPC messages, making the parallelism correspondence direct.

Load-bearing premise

The whole resource analysis rests on the existence of a locality-sensitive hash family with quality ρ < 1/3 for the key–query metric; if the best achievable quality is at least 1/3, the hash-table count stops being sublinear and the subquadratic-time and near-linear-machine claims collapse.

What would settle it

Find a Euclidean LSH family with quality ρ ≥ 1/3 for some c > √3 and show that Algorithm 1 then requires Ω(N²) time, since ℓ = Θ(N^{3ρ} log N) becomes linear or worse; alternatively, exhibit a sequence of inputs where the observed number of hash collisions per query grows like N^{3ρ} with ρ ≥ 1/3, contradicting the runtime bound.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

Conditional MPC round lower bounds (e.g., for graph connectivity and k-hop) transfer to ANNA-transformers, so fast attention inherits known parallelism limits.
A one-layer, one-head, embedding-dimension-1 ANNA transformer solves Match2, showing exact-match retrieval is enough for basic associative reasoning.
ANNA solves k-hop induction heads with O(log k) depth and sublinear width, exceeding what low-rank or recurrent models can do at comparable size.
Any low-rank attention transformer of depth L can be simulated by an O(L)-layer ANNA transformer, so low-rank approximations add no representational power beyond ANNA under sublinear rank.
The near-linear machine count in the MPC simulation means efficient attention has the same coarse parallel expressiveness as standard attention without the prior quadratic-machine overhead.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the ANNA/MPC equivalence extends to training rather than existence constructions, LSH-based attention could serve as a principled substitute for standard attention in long-context architectures with representational guarantees.
The dependence on ρ<1/3 means practical speedups hinge on the LSH family's quality; alternative metrics or data distributions with worse separation may require more hash tables and erode the subquadratic guarantee.
The simulation of low-rank attention via MPC suggests a unified design recipe: any efficient attention that is effectively sparse-plus-low-rank can be upgraded to ANNA without losing representational power.
A testable extension is to benchmark distilled ANNA transformers on real long-context tasks to see whether the theoretical near-linear machine/round equivalence correlates with actual scaling behavior.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Real theoretical advance in efficient-attention expressivity, with a fixable-but-real gap in the ANNA definition around empty neighborhoods.

read the letter

The two theorems that matter here are Theorems 4.1 and 4.2: ANNA-transformers and MPC are equivalent up to near-linear machine counts, close enough to close the N^2-machine gap left by Sanford et al. This is genuinely new — prior LSH-attention work gave algorithms, not sharp representational characterizations — and the low-rank-to-ANNA simulation plus the k-hop depth separation are credible contributions. I checked the central constructions by hand: EMA as the r=0, c->infinity limit is coherent, the routing lemma does route messages through exact-match attention, and the MPC simulation of the LSH implementation via sorting per hash table is plausible.

Now the soft spots, in order of seriousness.

First, the stress-test note about Definition 3.3 is correct: ANNA requires row weights to sum to 1, but EMA returns the zero vector when no key matches. Those unmatched rows are not convex combinations of value vectors, so they are not valid ANNA mechanisms as defined. This is not a corner case: the MPC routing construction uses EMA in heads where a given machine may receive no message, and the Match2 construction explicitly relies on outputting 0 for unmatched queries. The paper never supplies a fallback dummy key or relaxes the definition. The fix is straightforward — add a dummy key with zero value, or allow degenerate zero-sum rows — but as written the theorems are formally false for the empty-neighborhood case. This is the most important issue for the authors to repair.

Second, several proofs are compressed to the point of sloppiness. The union bound in Theorem A.1 glosses over correlations across hash tables; Algorithm 1's stated runtime drops the factor of z (the number of hash functions per table), so it should be O(m N^{1+3rho} log^2 N), not O(m N^{1+3rho} log N); and Theorem C.3's proof sketch jumps from hash values to machine indices without accounting for the sorted-order mapping. None of these look fatal, but they are exactly the places where a reader will lose confidence.

Third, the experiments are toy-scale and underreported: no code, no variance, best-over-z reported, no teacher-model baseline, and only small synthetic lengths. Since the contribution is theoretical, this is a minor blemish, not a reason to reject.

The LSH quality assumption rho<1/3 is standard given c>sqrt(3) and the Andoni-Indyk bounds; I do not see a problem there.

Bottom line: the paper deserves a serious referee. The central claims are likely correct and the unification of LSH- and low-rank-efficient attention under MPC is worth having. I would require the authors to patch the empty-neighborhood definition and tighten the cited proofs before it is publication-ready, but I would not desk-reject it.

Referee Report

2 major / 5 minor

Summary. The paper introduces Approximate Nearest Neighbor Attention (ANNA), an LSH-based sub-quadratic attention mechanism, and claims that ANNA-transformers preserve the representational equivalence between standard transformers and Massively Parallel Computation (MPC) established by Sanford et al., while reducing the N^2-machine gap in the transformer-to-MPC direction to near-linear for large approximation factor c. The main formal results are: (i) Theorem 4.1, an R-round (ε,ε)-MPC protocol can be simulated by an O(R)-layer ANNA-transformer of width O(N^{ε+δ}); (ii) Theorem 4.2, an L-layer ANNA-transformer of width N^ε can be simulated by an O(L)-round MPC protocol with N^{ε+δ} local memory and N^{1+ε-ε'+O(1/c^2)} machines; (iii) Theorem 4.4, low-rank attention transformers can be simulated by ANNA-transformers; and (iv) constructions for Match2 and k-hop with near-optimal depth, plus small-scale experiments on both tasks. The body and appendices give detailed proofs for the LSH implementation, the MPC simulations, and the reasoning tasks.

Significance. If the claims were fully correct as stated, this would be a substantial advance: it would show that a sub-quadratic attention mechanism can match the MPC representational power previously established only for quadratic softmax attention, and would provide a unified account of LSH-based and low-rank efficient attention mechanisms. The paper also gives explicit machine counts and round counts rather than only asymptotic existence arguments, and it identifies a concrete separation between ANNA and low-rank attention on k-hop. These are valuable contributions. However, the load-bearing connections rely on a special-case reduction to Exact-Match Attention that is not valid under the paper's own Definition 3.3 for unmatched queries, and the headline equivalence is conditional on an LSH quality bound that is not stated in Theorem 1.1. Both issues are fixable but currently affect the main theorems.

major comments (2)

[Definition 3.3; Appendix B; §5.1] The claimed special case EMA ⊆ ANNA fails for queries with empty neighborhoods. Definition 3.3 requires ∑_j w_{i,j}=1 for every row, but Definition B.1 sets EMA(q_i)=0 when no key equals q_i, which is not a convex combination of value vectors. The routing lemma (Lemma B.3), the MPC simulation (Theorem B.2/Corollary B.9), and the Match2 construction (Theorem F.1/Corollary F.2) all rely on exactly this 0-output behavior. Hence Theorem 4.1 and Theorem 5.2 are not established as stated for inputs with unmatched queries/keys. Please add an explicit fallback/dummy key with zero value (or otherwise relax Definition 3.3 for empty neighborhoods) and re-verify the affected proofs; the current text contains no such provision.
[Theorem 3.4 / Theorem 4.2 / Theorem 1.1] The headline equivalence is conditional on an LSH quality assumption that is not reflected in Theorem 1.1. Theorem 3.4 explicitly fixes c>√3 and an LSH family with ρ<1/3, and the proof of Theorem C.3 sets ρ=1/c². For small c (e.g., c close to 1), the required LSH family is not known to exist, and the machine count N^{1+ε-ε'+3/c²} can be far above quadratic. Please restrict Theorems 4.2 and 1.1 to the regime where the LSH guarantee applies, or state the result parametrically as a function of the achievable LSH quality ρ, and make this condition explicit in the informal theorem.

minor comments (5)

[Section 3.2] The sentence 'ANNA layers and ANNA transformers are defined in a completely analogous fashion as (standard) attention layers and transformers are defined (Theorems 2.1 and 2.2)' should refer to Definitions 2.1 and 2.2, not Theorems.
[Algorithm 1, line 14] The division v_sum/count is undefined when a query's bucket is empty. This is a concrete manifestation of the empty-neighborhood issue; the algorithm should specify a fallback or define the output as 0 in that case.
[Title page] Minor typo in affiliation: 'San Franciso' should be 'San Francisco'.
[Section 5.3 / Appendix G] The experiments distill from a trained softmax surrogate into an ANNA implementation; they do not directly train Algorithm 1. This is stated in Appendix G, but the main text should make it clearer in Figure 1's caption so readers do not interpret the reported errors as end-to-end ANNA training.
[Theorem 4.2] The theorem treats the ANNA transformer as a deterministic object after fixing the random seeds for the LSH hash functions. Please state explicitly that the equivalence holds for every fixing of the random bits, since Algorithm 1 is randomized.

Circularity Check

0 steps flagged

No circular reduction: the ANNA-MPC equivalence is proved by explicit constructions, and the imported self-cited lemmas are independent prior technical results. A definitional gap around EMA's zero output is a soundness issue, not a circularity.

full rationale

The paper's central claims are proved by explicit constructions rather than by assuming the conclusion. Theorem 4.2 simulates each ANNA layer by sorting queries and keys by LSH hash values and aggregating bucket sums/counts in MPC (Appendix C); Theorem 4.1 constructs EMA routing heads that encode each MPC message and retrieve by exact-match keys (Appendix B). The low-rank simulation (Theorem 4.4) goes through an independently built MPC protocol for low-rank attention (Lemma D.2) and then the MPC-to-ANNA theorem. No fitted parameter is later renamed as a prediction, and no theorem is obtained by restating its own definition. The paper does import two lemmas from prior work by overlapping authors (Lemma B.4 from Sanford et al. 2024c and Lemma B.12/Proposition 24 from Sanford et al. 2024a), and these are load-bearing subroutines. However, they are published results with stated assumptions that do not include the ANNA-MPC equivalence; they are standard technical tools (sparse-averaging error-correction encoding and a communication-capacity reduction for MPC), so under the reviewing rules they count as real external evidence and do not by themselves make the derivation circular. The LSH quality rho < 1/3 is an explicit stated condition (Theorem 3.4) backed by the external Andoni-Indyk LSH guarantee, again not a circular import. Separately, the manuscript contains a non-circular soundness gap that should be weighed in any correctness review: Definition 3.3 requires sum_j w_ij = 1, while Definition B.1 defines EMA(q_i)=0 when no key equals the query, and Algorithm 1 divides by count=0 for empty buckets. Thus the claimed 'EMA is a special case of ANNA' step, and the Match2/MPC constructions that rely on zero output for unmatched queries, are not justified for empty neighborhoods without an explicit fallback. This affects the validity of Theorems 4.1 and 5.2 as written, but it is a definitional/edge-case bug rather than a prediction reducing to its inputs, so it does not raise the circularity score. The stated limitations in Section 6 (ad hoc training, small synthetic experiments) are honest and do not mask any circular reasoning.

Axiom & Free-Parameter Ledger

2 free parameters · 5 axioms · 2 invented entities

The paper's central theorems rest on standard MPC definitions, published LSH results, and two imported lemmas from the same research group's prior work (Sanford et al. 2024a,c): the communication-capacity simulation lemma (Prop. 24) and the sparse message-encoding lemma (Lemma 3.2). These are not proved in the text but are peer-reviewed elsewhere. The mechanism parameters c and ell are design choices rather than fitted constants; the experimental hyperparameters are tuned on the small synthetic tasks only.

free parameters (2)

ANNA approximation factor c (equivalently LSH quality rho = 1/c^2) = c > sqrt(3), e.g., c >= 10 in practice
Governs the speed/accuracy tradeoff: sub-quadratic runtime requires rho < 1/3, and the machine count in Theorem 4.2 is N^(1+epsilon-epsilon'+3/c^2). Chosen as a design parameter, not fitted to data.
Experiment hyperparameters (beta, ell, z, learning rate) = beta=0.1 (Match2), beta=1 (induction heads); ell and z swept; LR 0.01
Tuned on the small synthetic tasks in Section 5.3; they affect only the empirical demonstration, not the theorems.

axioms (5)

domain assumption Bit-precision and arbitrary elementwise computation: Q, K, V, psi may be arbitrary functions, limited only by p = Theta(log N) bit precision
Required for the MPC equivalence; inherited from Sanford et al. 2024c (Section 2.1 and footnote 1), stated in this paper's Section 2.2.
standard math LSH family with quality rho < 1/3 exists for Euclidean space (Andoni-Indyk 2006 achieves rho = 1/c^2 + o(1))
Needed for Theorem 3.4's sub-quadratic runtime and for Theorem 4.2's near-linear machine count.
domain assumption Any (gamma, epsilon)-MPC can be simulated by an O(N^rho)-communication-capacity (gamma, epsilon, rho)-MPC (Proposition 24 of Sanford et al. 2024a)
Imported lemma used in Theorem B.10 / Corollary B.14 to obtain width O(N^epsilon') and in the k-hop and induction-head depth bounds.
domain assumption Message-encoding lemma (Lemma 3.2 of Sanford et al. 2024c): messages can be encoded in R^(O(alpha^4 Delta log q)) so that averaging collisions can be decoded
Used in Lemma B.3 (routing) with alpha = Delta = s; drives the embedding dimension O(s^5 log q).
standard math MPC sorting in O(1/(epsilon'-epsilon)) rounds with O(N^(1+epsilon-epsilon')) machines (Goodrich et al. 2011)
Used in the MPC simulations of EMA and ANNA (Theorems C.1 and C.3).

invented entities (2)

ANNA (Approximate Nearest Neighbor Attention) mechanism no independent evidence
purpose: Efficient attention mechanism defined by weight constraints (Definition 3.3), intended to be implementable in sub-quadratic time via locality-sensitive hashing
The paper proves its properties internally; there is no external falsifiable handle beyond the stated theorems and the small synthetic experiments.
Exact-Match Attention (EMA) no independent evidence
purpose: A special case of ANNA (r=0, c to infinity) that routes MPC messages via exact key matching, implementable by sorting in near-linear time
Defined and analyzed within this paper as the engine for the ANNA-simulates-MPC direction.

reviewed 2026-08-04 · how reviews work

0 comments

Cite this review

Pith. "Pith review of Fast attention mechanisms: a tale of parallelism." pith.science (2026). https://pith.science/paper/FEIDO233

@misc{pith2026250909001,
  author       = {Pith},
  title        = {Pith review of: Fast attention mechanisms: a tale of parallelism},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FEIDO233}},
  note         = {Machine review of arXiv:2509.09001}
}

Share X Bluesky LinkedIn Reddit HN

read the original abstract

Transformers have the representational capacity to simulate Massively Parallel Computation (MPC) algorithms, but they suffer from quadratic time complexity, which severely limits their scalability. We introduce an efficient attention mechanism called Approximate Nearest Neighbor Attention (ANNA) with sub-quadratic time complexity. We prove that ANNA-transformers (1) retain the expressive power previously established for standard attention in terms of matching the capabilities of MPC algorithms, and (2) can solve key reasoning tasks such as Match2 and $k$-hop with near-optimal depth. Using the MPC framework, we further prove that constant-depth ANNA-transformers can simulate constant-depth low-rank transformers, thereby providing a unified way to reason about a broad class of efficient attention approximations.

Figures

Figures reproduced from arXiv: 2509.09001 by Alexandr Andoni, Clayton Sanford, Daniel Hsu, Hantao Yu, Jingwen Liu.

discussion (0)

Forward citations

Cited by 1 Pith paper

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

Scaling Laws for Grid-Based Approximate Nearest Neighbor Search in High Dimensions
cs.LG 2026-07 unverdicted novelty 6.0

Multiprobe grid ANN maintains roughly constant d-scaling on GloVe while graph/tree/partitioning methods degrade, with near-linear N scaling and lower indexing cost.

Reference graph

Works this paper leans on

17 extracted references · 1 linked inside Pith · cited by 1 Pith paper

[1]

The input feeded into EMA-transformer is distributed in theN tokens, and we need to transfer than into the first⌈N s ⌉tokens/machines to matchMachineIn 1

Initialization. The input feeded into EMA-transformer is distributed in theN tokens, and we need to transfer than into the first⌈N s ⌉tokens/machines to matchMachineIn 1
[2]

After the local computation in each roundr, we need to communicate the messages fromMachineOutr toMachineIn r+1

Routing (message transmission). After the local computation in each roundr, we need to communicate the messages fromMachineOutr toMachineIn r+1
[3]

Consider the family G with Prg∈G[g(x) = g(y)] ≤ 0.1 N 3, if ∥x−y∥> cr

Since we only want the nearest neighbors within distancecr with the query point, we want to bound the probability of two points with distance greater thancr to fall into the same bucket. Consider the family G with Prg∈G[g(x) = g(y)] ≤ 0.1 N 3, if ∥x−y∥> cr . Then for each bucket, the expected number of collision (x, yfall into the same bucket and∥x−y∥> cr...

1998
[4]

32 For step 1, each machine only needs to send message to its neighbor machine: machinei sends message to machinei− 1, and this only takes 1 round

Send each( i, wσ(w,i), σ(w, i))to the correct output machine⌈ i s ⌉ and output wσ(w,i) for token i. 32 For step 1, each machine only needs to send message to its neighbor machine: machinei sends message to machinei− 1, and this only takes 1 round. In step 2, each tuple is onlyO(logN )bits, so by Theorem C.2, the sorting takesO( 1 ε )rounds. In step 3, aga...
[7]

validity bit

Final output. The MPCoutput is distributed in the first⌈ N s ⌉ tokens/machines, and we need to distributed them back to the N tokens. The following 3 lemmas construct the elements for each of these 3 parts. We first show the message transmission part of MPC can be simulate by the EMA-transformer. Recall that afterr rounds of local computation, each machin...

2019
[8]

Apply a hash functionh:R m →Uon{q 1, . . . , qN }
[9]

Sort all qi’s (and thuski’s) by h(qi)and partition all qi’s into chunks of sizeB≤O (1), and let h′(qi)be the label of the chunk thatqi is in (the queries in each chunk can have different hash values)
[10]

The output embedding forqi is therefore X j:h′(kj )=h′(qi) exp(⟨qi, kj⟩)X j′:h′(kj′ )=h′(qi) exp(⟨qi, kj′⟩) ·v j

For eachqi, only attend tokj’s such that they are in the same chunk. The output embedding forqi is therefore X j:h′(kj )=h′(qi) exp(⟨qi, kj⟩)X j′:h′(kj′ )=h′(qi) exp(⟨qi, kj′⟩) ·v j. We define fℓ : [ N ] → [N ]B as the function that specifies the set of keys each query should compute inner product with in theℓ-th layer. From the Reformer constraints, we h...
[11]

In theℓ-th layer attention computation for each queryqi, Reformer computes X j∈fℓ(i) exp(⟨qi, kj⟩)X j′∈fℓ(i) exp(⟨qi, kj′⟩) ·v j

For anyj∈f ℓ(i),f ℓ(j) =f ℓ(i). In theℓ-th layer attention computation for each queryqi, Reformer computes X j∈fℓ(i) exp(⟨qi, kj⟩)X j′∈fℓ(i) exp(⟨qi, kj′⟩) ·v j. We first study a restricted version of Reformer that fix the communication pattern beforehand i.e. fℓ is input-independent for allℓ∈ [L], and show that it can not compute the sum of all the input...
[12]

For each xi, retrieve the next tokenxi+1 and each token on the machine is stored as the embedding of(x i, i, xi+1, i+ 1)
[13]

Define a comparator< for the object(xi, i, xi+1, i+ 1). For two tuples(xi, i, xi+1, i+ 1)and (xj, j, xj+1, j+ 1), ifxi ̸= xj, then xi < xj ⇒ (xi, i, xi+1, i+ 1) < (xj, j, xj+1, j+ 1); ifxi = xj, then i < j⇒(xi, i, xi+1, i+ 1) < (xj, j, xj+1, j+ 1). Sort( xi, i, xi+1, i+ 1)by the comparator <
[14]

Each token( xi, i, xi+1, i+ 1)in the sorted list retrieves the token before it in the sorted list, denoted by( xj, j, xj+1, j+ 1). Update the embedding of token: ifxj = xi, the embedding of the token xi becomes( i, xj+1, j+ 1)i.e.( i, wσ(w,i), σ(w, i)); if wj ̸= wi, then the embedding of the tokenx i becomes(i,⊥,0)
[16]

ifk ℓ = 0, tokeniis updated as:(i, t 1, t2, wσk:ℓ (w,i), σk:ℓ(w, i))
[17]

Therefore, the total round isO( 1 ε ) + 2(ℓ + 1)

ifk ℓ = 1, tokeniis updated as:(i, t 1, t2, t3, t4) By definition, the embedding of tokeninow is: (i, wσ2ℓ+1 (w,i), σ2ℓ+1 (w, i), wσk:ℓ+1 (w,i), σk:ℓ+1(w, i)) The above inductive step only takes 2 rounds of MPC. Therefore, the total round isO( 1 ε ) + 2(ℓ + 1). Whenℓ=⌊logk⌋+ 1, this algorithm compute the output fork-hop. Again, we can convert this MPC alg...

2015
[2023]

Andreas Loukas

URLhttps://openreview.net/forum?id=De4FYqjFueZ. Andreas Loukas. What graph neural networks cannot learn: depth vs width. InInternational Confer- ence on Learning Representations, 2020. URLhttps://openreview.net/forum?id=B1l2bp4YwS. William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers.Transactions of the...

Pith/arXiv arXiv 2020
[2024]

Nathan Linial

URLhttps://openreview.net/forum?id=3EWTEy9MTM. Nathan Linial. Locality in distributed graph algorithms.SIAM Journal on computing, 21(1):193–201, 1992. Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learnshortcutstoautomata. InThe Eleventh International Conference on Learning Representations,

1992
[2025]

Kai Yang, Jan Ackermann, Zhenyu He, Guhao Feng, Bohang Zhang, Yunzhen Feng, Qiwei Ye, Di He, and Liwei Wang

URLhttps://openreview.net/forum?id=h3wbI8Uk1Z. Kai Yang, Jan Ackermann, Zhenyu He, Guhao Feng, Bohang Zhang, Yunzhen Feng, Qiwei Ye, Di He, and Liwei Wang. Do efficient transformers really save computation? In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors,Proceedings of t...

2024

This paper was first reviewed by deepseek-v4-flash on August 4, 2026.

[1] [1]

The input feeded into EMA-transformer is distributed in theN tokens, and we need to transfer than into the first⌈N s ⌉tokens/machines to matchMachineIn 1

Initialization. The input feeded into EMA-transformer is distributed in theN tokens, and we need to transfer than into the first⌈N s ⌉tokens/machines to matchMachineIn 1

[2] [2]

After the local computation in each roundr, we need to communicate the messages fromMachineOutr toMachineIn r+1

Routing (message transmission). After the local computation in each roundr, we need to communicate the messages fromMachineOutr toMachineIn r+1

[3] [3]

Consider the family G with Prg∈G[g(x) = g(y)] ≤ 0.1 N 3, if ∥x−y∥> cr

Since we only want the nearest neighbors within distancecr with the query point, we want to bound the probability of two points with distance greater thancr to fall into the same bucket. Consider the family G with Prg∈G[g(x) = g(y)] ≤ 0.1 N 3, if ∥x−y∥> cr . Then for each bucket, the expected number of collision (x, yfall into the same bucket and∥x−y∥> cr...

1998

[4] [4]

32 For step 1, each machine only needs to send message to its neighbor machine: machinei sends message to machinei− 1, and this only takes 1 round

Send each( i, wσ(w,i), σ(w, i))to the correct output machine⌈ i s ⌉ and output wσ(w,i) for token i. 32 For step 1, each machine only needs to send message to its neighbor machine: machinei sends message to machinei− 1, and this only takes 1 round. In step 2, each tuple is onlyO(logN )bits, so by Theorem C.2, the sorting takesO( 1 ε )rounds. In step 3, aga...

[5] [7]

validity bit

Final output. The MPCoutput is distributed in the first⌈ N s ⌉ tokens/machines, and we need to distributed them back to the N tokens. The following 3 lemmas construct the elements for each of these 3 parts. We first show the message transmission part of MPC can be simulate by the EMA-transformer. Recall that afterr rounds of local computation, each machin...

2019

[6] [8]

Apply a hash functionh:R m →Uon{q 1, . . . , qN }

[7] [9]

Sort all qi’s (and thuski’s) by h(qi)and partition all qi’s into chunks of sizeB≤O (1), and let h′(qi)be the label of the chunk thatqi is in (the queries in each chunk can have different hash values)

[8] [10]

The output embedding forqi is therefore X j:h′(kj )=h′(qi) exp(⟨qi, kj⟩)X j′:h′(kj′ )=h′(qi) exp(⟨qi, kj′⟩) ·v j

For eachqi, only attend tokj’s such that they are in the same chunk. The output embedding forqi is therefore X j:h′(kj )=h′(qi) exp(⟨qi, kj⟩)X j′:h′(kj′ )=h′(qi) exp(⟨qi, kj′⟩) ·v j. We define fℓ : [ N ] → [N ]B as the function that specifies the set of keys each query should compute inner product with in theℓ-th layer. From the Reformer constraints, we h...

[9] [11]

In theℓ-th layer attention computation for each queryqi, Reformer computes X j∈fℓ(i) exp(⟨qi, kj⟩)X j′∈fℓ(i) exp(⟨qi, kj′⟩) ·v j

For anyj∈f ℓ(i),f ℓ(j) =f ℓ(i). In theℓ-th layer attention computation for each queryqi, Reformer computes X j∈fℓ(i) exp(⟨qi, kj⟩)X j′∈fℓ(i) exp(⟨qi, kj′⟩) ·v j. We first study a restricted version of Reformer that fix the communication pattern beforehand i.e. fℓ is input-independent for allℓ∈ [L], and show that it can not compute the sum of all the input...

[10] [12]

For each xi, retrieve the next tokenxi+1 and each token on the machine is stored as the embedding of(x i, i, xi+1, i+ 1)

[11] [13]

Define a comparator< for the object(xi, i, xi+1, i+ 1). For two tuples(xi, i, xi+1, i+ 1)and (xj, j, xj+1, j+ 1), ifxi ̸= xj, then xi < xj ⇒ (xi, i, xi+1, i+ 1) < (xj, j, xj+1, j+ 1); ifxi = xj, then i < j⇒(xi, i, xi+1, i+ 1) < (xj, j, xj+1, j+ 1). Sort( xi, i, xi+1, i+ 1)by the comparator <

[12] [14]

Each token( xi, i, xi+1, i+ 1)in the sorted list retrieves the token before it in the sorted list, denoted by( xj, j, xj+1, j+ 1). Update the embedding of token: ifxj = xi, the embedding of the token xi becomes( i, xj+1, j+ 1)i.e.( i, wσ(w,i), σ(w, i)); if wj ̸= wi, then the embedding of the tokenx i becomes(i,⊥,0)

[13] [16]

ifk ℓ = 0, tokeniis updated as:(i, t 1, t2, wσk:ℓ (w,i), σk:ℓ(w, i))

[14] [17]

Therefore, the total round isO( 1 ε ) + 2(ℓ + 1)

ifk ℓ = 1, tokeniis updated as:(i, t 1, t2, t3, t4) By definition, the embedding of tokeninow is: (i, wσ2ℓ+1 (w,i), σ2ℓ+1 (w, i), wσk:ℓ+1 (w,i), σk:ℓ+1(w, i)) The above inductive step only takes 2 rounds of MPC. Therefore, the total round isO( 1 ε ) + 2(ℓ + 1). Whenℓ=⌊logk⌋+ 1, this algorithm compute the output fork-hop. Again, we can convert this MPC alg...

2015

[15] [2023]

Andreas Loukas

URLhttps://openreview.net/forum?id=De4FYqjFueZ. Andreas Loukas. What graph neural networks cannot learn: depth vs width. InInternational Confer- ence on Learning Representations, 2020. URLhttps://openreview.net/forum?id=B1l2bp4YwS. William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers.Transactions of the...

Pith/arXiv arXiv 2020

[16] [2024]

Nathan Linial

URLhttps://openreview.net/forum?id=3EWTEy9MTM. Nathan Linial. Locality in distributed graph algorithms.SIAM Journal on computing, 21(1):193–201, 1992. Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learnshortcutstoautomata. InThe Eleventh International Conference on Learning Representations,

1992

[17] [2025]

Kai Yang, Jan Ackermann, Zhenyu He, Guhao Feng, Bohang Zhang, Yunzhen Feng, Qiwei Ye, Di He, and Liwei Wang

URLhttps://openreview.net/forum?id=h3wbI8Uk1Z. Kai Yang, Jan Ackermann, Zhenyu He, Guhao Feng, Bohang Zhang, Yunzhen Feng, Qiwei Ye, Di He, and Liwei Wang. Do efficient transformers really save computation? In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors,Proceedings of t...

2024

Fast attention mechanisms: a tale of parallelism

The reading

Core claim §

What carries the argument

Load-bearing premise §

What would settle it §

If this is right

Where Pith is reading between the lines

discussion (0)

Core claim

Load-bearing premise

What would settle it