Two Heads Are Better than One: Simulating Large Transformers with Small Ones

Hantao Yu; Josh Alman

REVIEW 4 major objections 5 minor 41 references

Two Heads Are Better than One: Simulating Large Transformers with Small Ones

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read This paper proves that any transformer that reads a long input of length N can be simulated by a small transformer that only reads short inputs of length M, using O((N/M)^2) oracle calls in the worst case and O(N/M) under average-case or…

desk verdict A genuinely new oracle model for decomposing long-context transformers into small-transformer calls; the worst-case quadratic bound is solid, the linear-case results have fixable proof gaps, and the MLP assumptions are explicit but strong. read the letter →

arxiv 2506.12220 v2 pith:TEZSFBSP submitted 2025-06-13 cs.LG cs.AI

Hantao Yu , Josh Alman This is my paper · ORCID

classification cs.LGcs.AI MSC 68T0768Q17

keywords transformersimulationself-attentionlongcontextoraclecomplexityrepresentationalstrengthslidingwindowattentionsinkslowerbounds

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to establish that long-context transformer computation can be decomposed into many short-context transformer computations without sacrificing expressive power. The main theorem states that any transformer with input length $N$, $L$ layers, $H$ heads per layer, and embedding dimension $d$ is simulated by $O((N/M)^2 \cdot HL/(H'L'))$ calls to a transformer oracle that accepts only length-$M$ inputs, with embedding dimension $O(dH'L'/H)$; the oracle parameters are mostly shared with the original transformer, so the total parameter count grows by only a constant factor. The worst-case quadratic call count is shown to be necessary. When attention coefficients are bounded, or when attention uses sliding windows or attention sinks, the paper proves that the linear $O(N/M)$ number of calls suffices. If correct, the results mean long-context workloads could be run on hardware tuned for short sequences, with only a constant parameter overhead.

What carries the argument

The load-bearing objects are the block decomposition of the attention matrix and a normalization-recovery trick. For each length-$M$ query interval and each length-$M$ key interval, the algorithm constructs an oracle input whose softmax output encodes the unnormalized block sum $A_{i,t}$ through the ratio $A_{i,t}/(A_{i,t}+1)$; a synthetic token supplies the known $+1$. A second lemma packs $H'L'$ independent single-head, single-layer transformers into one oracle by giving each layer its own coordinate block and choosing attention weights that leave the other blocks unchanged. A third ingredient is a lookup-table lemma that lets oracle calls reorder or index tokens, which is what powers the random-permutation estimator for average-case inputs and the causal-masking constructions.

What would settle it

Run the normalization-recovery step of the main construction with a small transformer whose MLPs are fixed bounded-size ReLU networks instead of arbitrary functions, and test whether those networks can solve for $A_{i,t}$ from the output ratio $A_{i,t}/(A_{i,t}+1)$ and can perform the token reorderings required by the lookup-table lemma; if either fails, the claimed oracle calls will not produce the correct block sums.

Watch

Extended reading notes

Core claim

The central discovery is that the only serious obstacle to splitting a long attention computation into short blocks is the global normalization in softmax, and that obstacle can be removed by adding one synthetic token to the oracle input. The algorithm partitions the $N \times N$ attention matrix into blocks of size $M \times M$, one block per pair of query and key intervals. For each block, the oracle is fed a constructed sequence that includes a synthetic token with a known exponential score, so the output equals $A_{i,t}/(A_{i,t}+1)$; because the oracle's MLP is allowed to do division, the algorithm solves for the unnormalized sum $A_{i,t}$. Summing block contributions recovers the full softmax numerator and denominator, and the same construction is reused across all heads and layers by packing $H'L'$ independent single-head computations into one multi-layer, multi-head oracle. The parameters fed to the oracle mostly coincide with the original transformer's matrices, leaving only a constant factor blowup in the total number of parameters.

Load-bearing premise

The load-bearing premise is that the small transformer's MLP layers can perform arbitrary arithmetic such as division and exponentiation and can implement arbitrary token-indexing lookup tables; if real MLPs are weaker than that, the block-decomposition simulation does not go through.

Editorial extensions

If this is right

If the simulation is correct, long-context transformer inference becomes a sequence of short-context oracle calls, so accelerators optimized for lengths around $M$ could be used for much longer inputs.
When a short-context oracle runs in $O(M)$ wall-clock time rather than $O(M^2)$, the total wall-clock time of the quadratic simulation is $O(N^2/M)$.
The worst-case quadratic lower bound means a general simulation with fewer calls would contradict known hardness for approximating attention, so no uniformly cheaper decomposition exists.
Under bounded attention coefficients, $O(N/M)$ oracle calls give a $(1+\epsilon)$-approximation with high probability, providing a formal expressivity justification for chunked or hierarchical transformer-style processing.
Sliding-window attention and attention-sink masked transformers are simulatable with only $O(N/M)$ calls even for worst-case inputs, so these masked models are especially compatible with short-context execution.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A testable extension is to check whether trained hierarchical or chunked transformers satisfy the bounded attention-coefficient condition; if they do, the linear-call theorem predicts that chunkwise simulation should be accurate.
An empirical question the paper leaves open is whether the per-call overhead and matrix-assembly steps in the quadratic simulation are small enough on real hardware to beat direct long-context attention.
The oracle MLP assumption, which includes arbitrary division and lookup tables, is the strongest point of contact with practice; a natural next step is to determine which constructions survive when oracle MLPs are restricted to fixed-size ReLU networks.
Because oracle calls share most query, key, and value entries, the simulation maps naturally onto a distributed or parallel setting with one device per block and only $O(L)$ rounds of synchronization.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Josh, this one is worth your time. The paper introduces a new oracle model where you simulate a length-N transformer by making calls to a transformer that only takes length M, and proves two kinds of results. The headline is O((N/M)^2) calls suffice for any transformer, and that quadratic dependence is tight, following from the known attention lower bound. The block-decomposition construction in Lemma 3.1 is explicit: split the attention matrix into M-by-M blocks, use a synthetic token to recover the softmax denominator, and then combine. I checked the algebra; it works. The multi-head/multi-layer extension via Lemma 3.3 is also sound: pack H'L' independent single-head instances into one oracle's heads and layers using block-diagonal weights. This is the first provable expressivity guarantee for hierarchical transformer-style chunking, which is a real contribution.

The linear-call results for average-case inputs, sliding windows, and attention sinks are plausible but unevenly written. The aggregation step in the worst-case proof is dismissed as trivial when it needs a short argument. The sliding-window proof says later chunks follow identically without showing it. The concentration step in Theorem 4.1 uses sampling without replacement as if it were iid; that's fixable with standard Hoeffding for sampling without replacement, but it has to be written down. None of this looks fatal, but the paper needs a careful revision before I'd trust the linear bounds as stated.

On the complaint that the oracle MLP is too strong: that's partially fair but not a hidden flaw. The paper explicitly assumes oracle MLPs can do arbitrary arithmetic in O(d^2) time and can implement lookup tables. That is a strong assumption — a vanilla ReLU MLP with O(d^2) parameters is not shown to compute x/(1-x) to the claimed precision, and the imported lookup-table lemma needs arbitrary indexing functions. If you read the paper as a statement about practical hardware, the simulation may not go through. But in the representational-strength literature, this is the standard way to model MLPs, and the authors say so. They should be more upfront about how strong the oracle is, and say whether the O(d^2) parameter budget is actually enough for the required functions. That's a clarity issue, not a reason to reject.

Citations are fine. The one self-citation is to a published lower bound used only for the remark, not to define the target. The free parameter B in Theorem 4.2 is explicit.

Who is this for? People working on transformer expressivity, hierarchical models, or long-context inference theory. It deserves a serious referee. Send it out, but expect revisions to tighten the appendix and the oracle assumptions.

Referee Report

4 major / 5 minor

Summary. The paper studies simulating a large transformer with input length N by repeatedly invoking a small transformer oracle with input length M << N. The main result (Theorem 3.4) states that any transformer with L layers and H heads per layer can be simulated with O((N/M)^2 * HL/(H'L')) calls to an oracle with L' layers, H' heads, input length M, and embedding dimension O(dH'L'/H), with a matching worst-case lower bound. The paper also gives a linear number of calls under boundedness assumptions on attention weights (Theorem 4.1), and for sliding-window and attention-sink masking (Theorem 5.1). The proofs decompose the N x N attention matrix into M x M blocks, use synthetic tokens to recover normalization constants from softmax outputs, and pack independent single-layer, single-head instances into a multi-layer, multi-head oracle.

Significance. If the results hold in a realistic model, they provide a new decomposition of long-context transformer computation into short-context calls, with potential wall-clock speedups on hardware optimized for small contexts, and a theoretical justification for hierarchical chunking schemes. The paper's strengths include an explicit block-decomposition construction, a tight worst-case oracle-call count, parameter reuse with only constant-factor parameter blowup, and extensions to causal masking, sliding windows, and attention sinks. The main caveat is that the small transformer is an oracle whose MLPs are assumed to perform arbitrary arithmetic and lookup operations; this is a strong modeling assumption that should be stated prominently.

major comments (4)

[Section 2.1 and Lemma B.1] The simulation results are proved in an oracle model in which layer MLPs can perform arbitrary arithmetic operations (including exact division and inversion of the softmax ratio) and arbitrary lookup tables (Lemma A.3, imported from [SHT24]). These capabilities are load-bearing: Lemma B.1 recovers A_{i,t} from r = A_{i,t}/(A_{i,t}+1) by computing r/(1-r), and Theorem 4.1 uses Lemma A.3 to permute tokens. The paper does not show that these operations are realizable by a standard transformer MLP of size O(d^2), and with d=O(log N) and target error Theta(1/(2N)) in the approximate theorems, a universal-approximation invocation would require a precision analysis. The abstract and introduction present the result as simulation by 'transformers'; this should be qualified, or the realizability question should be addressed, because without these MLP powers the central construction does not go through.
[Lemma 3.3 / Appendix B.3] The proof that one L'-layer, H'-head oracle can simulate H'L' independent single-layer single-head transformers relies on the claim that 'the other parts are passed through the layer without being changed.' Under the paper's Definition 2.2 there is no residual connection: the layer MLP receives only the concatenated attention outputs, and an attention output is a softmax-weighted sum of value vectors. A weighted sum cannot in general reproduce the untouched input blocks, so the induction over L' layers is not justified. The proof must either add residual connections to the transformer model and re-derive the construction, or give an explicit attention-based identity-passing mechanism (for example, using Lemma A.3) that works for all rows with the same attention weights that also compute the desired instance.
[Lemma B.1 and Claim B.6] Several constructions feed the oracle a sequence of length M+1 while the oracle is specified to accept input length at most M. In Step 1 of Lemma B.1 the input is X[S_t,:] together with one synthetic token; in the cross-block case the input is the horizontal concatenation [X[S_t,:], X[S_{t'},:]] plus a synthetic row, also M+1 rows. Claim B.6 has the same structure. This is a constant-factor issue and can likely be repaired by reserving one slot and processing M-1 real tokens per call, but the theorem statements and the call-count bounds need to be adjusted accordingly.
[Lemma B.1, final aggregation step] The final step of Lemma B.1 states that computing the weighted sum Sum_t (B_{i,t}/A_{i,t}) * A_{i,t} / Sum_t A_{i,t} 'can be done either trivially or with O((N/M)^2) oracle calls with Lemma A.2,' but the allowed outside-oracle operations are only padding and concatenation, not multiplication or division. No concrete sequence of oracle calls is given that arranges the per-block values into inputs of length at most M and aggregates them per query. Please specify this aggregation subroutine; as written, the proof of Theorem 3.4 is incomplete at this step.

minor comments (5)

[Theorem 4.1] The 'average-case' assumption is deterministic boundedness of all attention weights (1/C <= a_{i,j} <= C and a mean-dominance condition), not a distributional average-case model; the terminology could mislead readers.
[Lemma B.1] In the proof of Lemma B.1, S_t is defined as {(t-1)M, ..., tM}, whereas the notation section defines S_t = {(t-1)M+1, ..., tM}; the off-by-one should be fixed.
[Claim B.6] The displayed formula appears to have a typo: the denominator should be Sum_{j=1}^{i-1} a_{i-1,j} + exp(0), not Sum_{j=1}^{i} a_{i-1,j} + exp(0).
[Lemma A.2] The statement says the transformer computes a 1 x d sum, but the transformer output is N x d; the statement should say that every output row equals the sum.
[Section 1.2] The lower-bound discussion uses T both for the number of oracle calls and for the large transformer; please use distinct notation to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: upper bounds are explicit block-decomposition constructions; the cited prior lower bound and lookup lemma are independent support.

full rationale

The paper's main theorems are constructive: Lemma B.1 explicitly partitions the N×N attention matrix into M×M blocks, inserts a synthetic token with known attention mass, and algebraically recovers the unnormalized block sums; Step 2 computes output block ratios; Theorems B.4/B.5/C.1/D.1 then assemble these elementary simulations. None of these steps fits a parameter to a target quantity and then reports it as a prediction; the softmax-ratio inversion in Lemma B.1 is a stated capability of the oracle MLP ('They can do basic arithmetic operations... as long as they take O(d^2) time'), an explicit model assumption rather than a hidden circular definition. The lookup-table lemma A.3 is imported from SHT24 and is used only as a tool for token reordering; it is an external, stated-lemma result, not a restatement of the theorem being proved. The only self-citation is the use of AS24 for the worst-case lower bound; that is an independently published complexity lower bound whose assumptions (bounded entries, standard complexity hypotheses) do not include the number of small-transformer oracle calls, so it is real evidence rather than a circularity. The skeptical concern about whether bounded-size ReLU MLPs can exactly implement division/lookup is a modeling-realism question, not a circularity of the derivation chain.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

No new physical or mathematical entities are introduced. The free-parameter ledger is nearly empty because the constructions are parameter-free derivations from the given transformer. The main load-bearing assumptions are the power of MLPs inside the oracle, the imported lookup-table lemma, and the conditional complexity lower bound used for tightness.

free parameters (1)

B (Theorem 4.2) = poly(N), chosen sufficiently large
Embedding offset used to make cross-instance attention vanish; not fitted to data, any sufficiently large poly(N) value works to push the error to O(1/2^N).

assumptions (4)

domain assumption MLPs can compute arbitrary continuous functions and basic arithmetic operations (division, exp) in O(d^2) time
Used throughout, e.g., Lemma B.1 solves A = x/(1-x) inside the oracle MLP; standard in transformer expressivity literature but stronger than a practical trained MLP.
domain assumption A single-layer transformer can implement arbitrary lookup tables (Lemma A.3 from [SHT24])
Imported without proof; used for token permutation in Theorem C.1 and token reordering in Theorem B.5.
domain assumption Fast attention requires Omega(N^{2-o(1)}) time under standard complexity assumptions ([AS24])
Used in Section 1.2 to argue the O((N/M)^2) oracle-call bound is tight; conditional on prior complexity-theoretic results, one co-authored by the present authors.
domain assumption Numbers have O(log N)-bit representations and computations are exact in the unlimited-precision setting
Theorem 1.1 uses epsilon = 0 exact real arithmetic; the finite-precision setting allows epsilon = Theta(1/2^N). Stated in Section 1.1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Two Heads Are Better than One: Simulating Large Transformers with Small Ones." pith.science (2026). https://pith.science/paper/TEZSFBSP

@misc{pith2026250612220,
  author       = {Pith},
  title        = {Pith review of: Two Heads Are Better than One: Simulating Large Transformers with Small Ones},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TEZSFBSP}},
  note         = {Machine review of arXiv:2506.12220}
}

abstract

The quadratic complexity of self-attention prevents transformers from scaling effectively to long input sequences. On the other hand, modern GPUs and other specialized hardware accelerators are well-optimized for processing small input sequences in transformers during both training and inference. A natural question arises: can we take advantage of the efficiency of small transformers to deal with long input sequences? In this paper, we show that transformers with long input sequences (large transformers) can be efficiently simulated by transformers that can only take short input sequences (small transformers). Specifically, we prove that any transformer with input length $N$ can be efficiently simulated by only $O((N/M)^2)$ transformers with input length $M \ll N$, and that this cannot be improved in the worst case. However, we then prove that in various natural scenarios including average-case inputs, sliding window masking and attention sinks, the optimal number $O(N/M)$ of small transformers suffice.

Figures

Figures reproduced from arXiv: 2506.12220 by the authors.

**Figure 1.** Proof Roadmap 2.3 Notation Throughout the paper, we denote X ∈ R N×d as the input to the large transformer, where N is the input length and d is the embedding dimension. For a N × d matrix X, we use X[i, :] to denote its i-th row, X[:, j] to denote its j-th column, and X[i, j] to denote its (i, j)-th entry. Given sets S ⊆ [N], D ⊆ [d], we use X[S, :] to denote the submatrix consisting of the rows in S, X[:, D] to de… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 36 canonical work pages

[1]

Zoology: Measuring and improving recall in efficient language models

Simran Arora, Sabri Eyuboglu, Aman Timalsina, Isys Johnson, Michael Poli, James Zou, Atri Rudra, and Christopher Re. Zoology: Measuring and improving recall in efficient language models. In The Twelfth International Conference on Learning Representations , 2024

work page 2024
[2]

Fast attention requires bounded entries

Josh Alman and Zhao Song. Fast attention requires bounded entries. In Proceedings of the 37th International Conference on Neural Information Processing Systems , NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc

work page 2024
[3]

Fundamental limitations on subquadratic alternatives to transformers

Josh Alman and Hantao Yu. Fundamental limitations on subquadratic alternatives to transformers. In The Thirteenth International Conference on Learning Representations , 2025

work page 2025
[4]

On the A bility and L imitations of T ransformers to R ecognize F ormal L anguages

Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the A bility and L imitations of T ransformers to R ecognize F ormal L anguages. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) , pages 7096--7116, Online, November 2020. Association for Comp...

work page 2020
[5]

Separations in the representational capabilities of transformers and recurrent architectures

Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the representational capabilities of transformers and recurrent architectures. In The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024

work page 2024
[6]

Peters, and Arman Cohan

Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv:2004.05150 , 2020

arXiv 2004
[7]

An exploration of hierarchical attention transformers for efficient long document classification, 2022

Ilias Chalkidis, Xiang Dai, Manos Fergadiotis, Prodromos Malakasiotis, and Desmond Elliott. An exploration of hierarchical attention transformers for efficient long document classification, 2022

work page 2022
[8]

Colwell, and Adrian Weller

Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tam \' a s Sarl \' o s, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J. Colwell, and Adrian Weller. Rethinking attention with performers. In 9th International Conference on Learning Representations, ICLR 2021, V...

2021

Show all 41 references

[9]

End-to-end object detection with transformers

Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In Computer Vision – ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part I , page 21...

2020
[10]

Scaling language models: Methods, analysis & insights from training gopher

Google DeepMind. Scaling language models: Methods, analysis & insights from training gopher. CoRR , abs/2112.11446, 2021

2021 arXiv
[11]

Fu, Stefano Ermon, Atri Rudra, and Christopher R\' e

Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher R\' e . Flashattention: fast and memory-efficient exact attention with io-awareness. In Proceedings of the 36th International Conference on Neural Information Processing Systems , NIPS '22, Red Hook, NY, USA, 20...

2022
[12]

Etched is Making the Biggest Bet in AI

Etched . Etched is Making the Biggest Bet in AI . https://www.etched.com/announcing-etched, June 2024. Accessed on

2024
[13]

Mamba: Linear-time sequence modeling with selective state spaces

Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752 , 2023

2023 arXiv
[14]

Theoretical limitations of self-attention in neural sequence models

Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics , 8:156--171, 2020

2020
[15]

Hyperattention: Long-context attention in near-linear time

Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David Woodruff, and Amir Zandieh. Hyperattention: Long-context attention in near-linear time. In The Twelfth International Conference on Learning Representations , 2024

2024
[16]

Computational limits of low-rank adaptation (lo RA ) fine-tuning for transformer models

Jerry Yao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, and Han Liu. Computational limits of low-rank adaptation (lo RA ) fine-tuning for transformer models. In The Thirteenth International Conference on Learning Representations , 2025

2025
[17]

Multilayer feedforward networks are universal approximators

Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural Networks , 2(5):359--366, 1989

1989
[18]

On statistical rates and provably efficient criteria of latent diffusion transformers (dits)

Jerry Yao-Chieh Hu, Weimin Wu, Zhuoru Li, Sophia Pi, Zhao Song, and Han Liu. On statistical rates and provably efficient criteria of latent diffusion transformers (dits). In The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024

2024
[19]

Kakade, and Eran Malach

Samy Jelassi, David Brandfonbrener, Sham M. Kakade, and Eran Malach. Repeat after me: transformers are better than state space models at copying. In Proceedings of the 41st International Conference on Machine Learning , ICML'24. JMLR.org, 2024

2024
[20]

An image is worth 16x16 words: Transformers for image recognition at scale

Alexander Kolesnikov, Alexey Dosovitskiy, Dirk Weissenborn, Georg Heigold, Jakob Uszkoreit, Lucas Beyer, Matthias Minderer, Mostafa Dehghani, Neil Houlsby, Sylvain Gelly, Thomas Unterthiner, and Xiaohua Zhai. An image is worth 16x16 words: Transformers for image recognition at...

2021
[21]

RNGD preview: The world's most efficient AI chip for LLM inference

Hanjoon Kim. RNGD preview: The world's most efficient AI chip for LLM inference . https://furiosa.ai/blog/rngd-preview-furiosa-ai, 2024. Accessed on

2024
[22]

Reformer: The efficient transformer

Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020 . OpenReview.net, 2020

2020
[23]

Polysketchformer: fast transformers via sketching polynomial kernels

Praneeth Kacham, Vahab Mirrokni, and Peilin Zhong. Polysketchformer: fast transformers via sketching polynomial kernels. In Proceedings of the 41st International Conference on Machine Learning , ICML'24. JMLR.org, 2024

2024
[24]

Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang

Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transformers learn shortcuts to automata. In The Eleventh International Conference on Learning Representations , 2023

2023
[25]

On the expressive flexibility of self-attention matrices

Valerii Likhosherstov, Krzysztof Choromanski, and Adrian Weller. On the expressive flexibility of self-attention matrices. Proceedings of the AAAI Conference on Artificial Intelligence , 37(7):8773--8781, Jun. 2023

2023
[26]

Hierarchical transformers for multi-document summarization

Yang Liu and Mirella Lapata. Hierarchical transformers for multi-document summarization. In Anna Korhonen, David Traum, and Llu \'i s M \`a rquez, editors, Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics , pages 5070--5081, Florence, Ita...

2019
[27]

The parallelism tradeoff: Limitations of log-precision transformers

William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics , 11:531--545, 2023

2023
[28]

William Merrill, Ashish Sabharwal, and Noah A. Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics , 10:843--856, 2022

2022
[29]

Language models are few-shot learners

OpenAI. Language models are few-shot learners. In Proceedings of the 34th International Conference on Neural Information Processing Systems , NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc

2020
[30]

Hierarchical transformers for long document classification

Raghavendra Pappagari, Piotr Zelasko, Jesús Villalba, Yishay Carmiel, and Najim Dehak. Hierarchical transformers for long document classification. pages 838--844, 12 2019

2019
[31]

Representational strengths and limitations of transformers

Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers. In Proceedings of the 37th International Conference on Neural Information Processing Systems , NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc

2023
[32]

Transformers, parallel computation, and logarithmic depth

Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic depth. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024 . OpenReview.net, 2024

2024
[33]

What formal languages can transformers express? a survey

Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? a survey. Transactions of the Association for Computational Linguistics , 12:543--561, 2024

2024
[34]

Efficient transformers: A survey

Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey. ACM Comput. Surv. , 55(6), December 2022

2022
[35]

Schmidt, and Stephan Peitz

Ali Vardasbi*, Telmo Pessoa Pires*, Robin M. Schmidt, and Stephan Peitz. State spaces aren’t enough: Machine translation needs attention. In EAMT , 2023

2023
[36]

Gomez, ukasz Kaiser, and Illia Polosukhin

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems , NIPS'17, page 6000–6010, Red H...

2017
[37]

RNN s are not transformers (yet): The key bottleneck on in-context retrieval

Kaiyue Wen, Xingyu Dang, and Kaifeng Lyu. RNN s are not transformers (yet): The key bottleneck on in-context retrieval. In The Thirteenth International Conference on Learning Representations , 2025

2025
[38]

Lightseq2: Accelerated training for transformer-based models on gpus

Xiaohui Wang, Ying Xiong, Xian Qian, Yang Wei, Lei Li, and Mingxuan Wang. Lightseq2: Accelerated training for transformer-based models on gpus. arXiv preprint arXiv:2110.05722 , 2021

2021 arXiv
[39]

Efficient streaming language models with attention sinks

Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. In The Twelfth International Conference on Learning Representations , 2024

2024
[40]

Are transformers universal approximators of sequence-to-sequence functions? In International Conference on Learning Representations , 2020

Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sequence-to-sequence functions? In International Conference on Learning Representations , 2020

2020
[41]

Reddi, and Sanjiv Kumar

Chulhee Yun, Yin-Wen Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J. Reddi, and Sanjiv Kumar. O(n) connections are expressive enough: Universal approximability of sparse transformers. In NeurIPS , 2020

2020

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

Zoology: Measuring and improving recall in efficient language models

Simran Arora, Sabri Eyuboglu, Aman Timalsina, Isys Johnson, Michael Poli, James Zou, Atri Rudra, and Christopher Re. Zoology: Measuring and improving recall in efficient language models. In The Twelfth International Conference on Learning Representations , 2024

work page 2024

[2] [2]

Fast attention requires bounded entries

Josh Alman and Zhao Song. Fast attention requires bounded entries. In Proceedings of the 37th International Conference on Neural Information Processing Systems , NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc

work page 2024

[3] [3]

Fundamental limitations on subquadratic alternatives to transformers

Josh Alman and Hantao Yu. Fundamental limitations on subquadratic alternatives to transformers. In The Thirteenth International Conference on Learning Representations , 2025

work page 2025

[4] [4]

On the A bility and L imitations of T ransformers to R ecognize F ormal L anguages

Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the A bility and L imitations of T ransformers to R ecognize F ormal L anguages. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP) , pages 7096--7116, Online, November 2020. Association for Comp...

work page 2020

[5] [5]

Separations in the representational capabilities of transformers and recurrent architectures

Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the representational capabilities of transformers and recurrent architectures. In The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024

work page 2024

[6] [6]

Peters, and Arman Cohan

Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv:2004.05150 , 2020

arXiv 2004

[7] [7]

An exploration of hierarchical attention transformers for efficient long document classification, 2022

Ilias Chalkidis, Xiang Dai, Manos Fergadiotis, Prodromos Malakasiotis, and Desmond Elliott. An exploration of hierarchical attention transformers for efficient long document classification, 2022

work page 2022

[8] [8]

Colwell, and Adrian Weller

Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tam \' a s Sarl \' o s, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J. Colwell, and Adrian Weller. Rethinking attention with performers. In 9th International Conference on Learning Representations, ICLR 2021, V...

2021