Two Heads are Better than One: Simulating Large Transformers with Small Ones
Authors: Hantao Yu
Josh Alman
Venue: NeurIPS 2025 spotlight ()
Keywords: Transformers
theory
representational strength
Primary area: deep_learning

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.

Two Heads Are Better than One: Simulating Large Transformers with Small Ones
Hantao Yu
Josh Alman
Department of Computer Science Columbia University
Department of Computer Science Columbia University
New York, NY 10027 hantao,, yaliaaooub@ollmmmiaa edu
New York, NY 10027 josh@cs columbia edu
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 trans- formers) 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 ((N/M)²² transformers with input length M < N,, and that this cannot be improved in the worst case. However, 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.
Introduction
The transformer architecture 17]+ has revolutionized modern machine learning, natural language processing and computer vision. It achieves state-of-the-att performance on various tasks such as language reasoning [Dee21] Ope20), image recognition [KDW* 21 CMS*20) and many others. At the core of the transformer architecture is the attention mechanism, which captures correlations between all pairs of tokens. However, this is also major bottleneck for transformers, as the quadratic complexity (in both time and memory) of the attention mechanism prohibits effective scaling of transformers as the sequence grows in length. Moreover, it has been theoretically proved that the quadratic complexity cannot be avoided (under popular complexity-theoree -hheoretcc assumptions) [AS24). To address this fundamental issue, there has been fruitful literature the design of "subquadratic alternatives" to transformers, where researchers come up with mechanisms that replace the attention mechanism and take subquadratic time (usually close línear time) [KKL20 CLD+22 21 DFF+
KMZ24 BPC20 GD23). However, they usually have worse performance than standard transformers, especially downstream tasks and translation [VPSP23 (Y255)
In the meantime, modern GPUs are increasingly optimized for handling short-to-moderate transformer contexts 2 2FF+ Some companies are even producing specialized hardware for efficient transformer inference that have superior performance on inputs of length between 128 to 2048 [im244 Etc24). This approach motivates the following questions:
Can we use small transformers to perform tasks more efficiently than large transformers? Are (multiple) small transformers inherently capable of dealing with long contexts?
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

In this paper, we give positive answers to these questions through the lens of representational strength, which studies whether one can select parameters for transformers so that they can perform certain tasks of interest. The representational strength of transformers has been studied broadly in recent years [BHBK24 LAG+23 SHT24 MS23], and is believed that is one of the core reasons why transformers outperform previous architectures such as RNN and LSTM [WL225 AET 24 SHT23
Our problem can be stated as follows. Suppose that we have all the parameters of a large transformer T with input length N, as well as an input X that we would like to evaluate T on. However, to evaluate T(X), we are not allowed to perform any particularly complicated computations; we are restricted to simple operations, and to making use of a small transformer O (as an oracle) that can only take input sequences of length M < N. We can imput into O any sequence and parameters that we can easily compute, and obtain its output. Our goal is to minimize the number of calls to O that we need to obtain T(X) for arbitrary input X of length N.
Our main results show that roughly O ((N/M))² oracle calls suffice, which we show is optimal. In addition, our algorithm requires minimal processing outside of the oracle calls, and it has properties needed for efficient training and inference, including that the gradients of its parameters are easily computed, and that its oracle calls can be computed in parallel in only (L) rounds of adaptivity, where L is the number of layers in the large transformer T.
In addition, we show that in many scenarios arising in practice, such when certain masking schemes are used, or when the data is not "worst-case" and satisfies some boundedness guarantees, the enformatiion-hhoorticce
optimal (NN/M) oracle calls suffice.
Our results provide a new way to deal with long input sequences for transformers, as we prove that any computation performed by large transformers can be decomposed into computations that only use smaller transformers. If the oracles are implemented using a quadratic number of floating-poini operations, then our algorithm also still requires quadratic amount of foating-point operations. However, if modern GPUs enable faster transformer inference with respect to the "wall-clock" time when the input sequence is moort-to-modrraee then our algorithms allow faster wall-clock time inference. For example, if the oracle can compute the output using O(M) wall-clock time compared to the standard (M²) time, then the total wall-clock running time of our algorithms will be (N))
Our approach is fundamentally different from designing "subquadratic alternatives" to transformers [KL,2 CLD+21 BPC20 KMZ24 GD23). In particular, our algorithm preserves the represen- tational strength of transformers (or even improves it), whereas it has been shown that all the subquadratic alternatives to transformers will lose representational strength as they cannot capture all the pairwise relationship even approximately [AY55.
Now we define our model of computation and state our main contributions in more detail.
1.1 Computational Model for Simulating Large Transformers
We now describe our model of computation in more detail. We are careful to allow only very simple operations beyond oracle calls, to ensure that the vast majority of computation can be performed by efficient hardware for evaluating small transformers, and that the number of oracle calls accurately measures the complexity of the problem.
We are given a large transformer T with input length N, L layers, H attention heads in each layer, and embedding dimension d (all the parameters, including the query, key, value matrices in each of its attention head and multilayer perceptron functions). Throughout this paper, we assume that T., H & N, = O(lg N), 2log N) I M < o(N), and one can typically imagine M R VN. Our goal is design an algorithm that (approximately) output T(X) E R for arbitrary input X (length at most N).
We have limited set of operations can perform as part of the algorithm. We criticaly have access to a small transformer (oracle) O that can take as input a sequence of length at most M & N, as well as the parameters for a transformer which has L' layers and H' attention heads in each layer, and outputs the transformer evaluated on that sequence. Our algorithm is allowed to:
1. Feed the oracle O with input sequences and parameters which are currently in memory to obtain its output;
2

---

2. Processing: Edit existing vectors matrices in memory by padding at most O(d²) fixed numbers (constants independent of the input) to them, or arranging (concatenating) matrices in memory.
We also assume that all the numbers in imput matrices, parameters, and algorithms have O(log N) N representations. We say that such an algorithm simulates TT if it always outputs Y R Nxx xd such that
| T())(( < (x)
for all i E [N], and for very small error ( We want to design algorithms that simulate T with fewer oracle calls as possible. (Such an e essentially unavoidable in limited precision architectures, but we will see it will be very helpful in some algorithms below. We also emphasize that our main result, Theorem I.1 an exact computation in the unlimited precision scenario with e = 0.)
Notice that any such algorithm can be viewed composition of oracles and the padding function. Since we only allow for very simple processing, it is straightforward to compute the gradients of the padding functions, so training the large model could be done via computing the gradients of the small transformer oracles.
1.2
Main Results
Quadratic small transtormers are sufficient and necessary for worst-case inputs. As summa- rized below, our main result shows that any computation performed on a large transformer can be decomposed into multiple instances of computation performed on smaller transformers with the same computational complexity or floating- poating-point operations. Since the oracle can only tell us the final output instead of intermediate embeddings, might be somewhat surprising that we are able utilize all the layers in small transformers.
Theorem 1.1 (Theorem 3.4 Theorem 3.5 For any transformer' T with L layers, H attention heads in each layer, input length N. embedding dimension d, there exists an algorithm that simulates T HL
with O({ M )2 H' calls to a transformer oracle with L' layers, H' attention heads in each layer, input length M, embedding dimension O dH'L'). The result still holds when we add causal masking to both large and small transformers.
H
Notice that these simulations are right, and roughly (N/M)² oracle calls are necessary in the worst- case due to computational complexity constraints. To see this, note that when L H = =' H' = 1, straightforward algorithm can compute the responses T oracle calls in time only O Thus, since it is known that even approximation of large attention requires time 2(())-((1)) (under standard complexity- tthorretc assumptions) [AS24), must have T ((N/M))))~=())
One might be concerned with the fact that ((V/M)² small transformers have many more param- eters than one large transformer, since each transformer has ( parameters, independent of the sequence length. However, this not a problem because in our construction, we reuse the parameters such that the total number of parameters does not depend on N. In fact, all the query, key and value matrices that we feed into the oracle share most entries with the query, key, value matrices in the large transformer that are given. We ultimately only have small, constant factor blowup on the number of parameters.
Linear small transformers are weaker but sufficient with average-case inputs. Even though we cannot use ONN/M oracle calls simulate a large transformer the worst case, we show that is possible when we have reasonable additional assumptions on the queries, keys and values.
Theorem 1.2 (Informal version of Theorem 4.1). Let TT be a transformer with L layers, H attention heads in each layer, input length N and embedding dimension d. Suppose that the queries, keys and values in the attention heads are all somewhat bounded in how much they may differ from each other. Then, there exists an algorithm using O HL oracle calls to simulate T.
CDF split the input sequence into chunks of size M and send each chunk into transformer before aggregating the outputs. We give the first provable guarantees for this approach, showing that O(N/M) small transformers have approximately equal expressivity a large transformer when the input data satisfies our assumptions.
Models such as Hierarchical Transformers P/V 19
3

---

This provides possible explanation of the success of Hierarchical Transformers and relevant ideas from an expressivity viewpoint.
On the other hand, we supplement Theorem 1.2 with its converse, which shows that a linear number of small transformers are most as expressive as one large transformer for worst-case inputs (we only prove the statement for single-head transformers to illustrate the message). As a result, when the inputs follow assumptions in Theorem 1.2 linear number of small transformers are equivalent to
larger one in expressive power.
Theorem 1.3 (Theorem 4.2). Given N/M instances of single layer, single head transformers with
input length M and embedding dimension d, there exists algorithm that simulates them with one call of single layer, single head transformer with input length ((N) and embedding dimension Odd) along with (NNMM) many matrix multiplications of size M x d x d.
We briefly comment on the small matrix multiplications in Theorem L.3 Note that they could be computed in the straightforward way in nearly linear time (Md)) (since d Oloo N)) and thus do not substantially contribute to the total running time. This implies, in particular, that they could not simulate the transformer oracles on their own, and are only "assisting" the large transformer oracle. Their presence seems unavoidable because of the ((NM)) weight matrices of the oracles which must be simulated by a single large transformer, which only has constant number of weight matrices. Moreover, we emphasize that our other constructions are even simpler, and do not need such small matrix computations outside of the oracle calls.
Efficient simulation of transformers with sliding window and StreamingL Sliding window and StreamingLLM [XTC*24] are popular ways to make transformer inference more memory efficient. Both sliding window and StreamingLLMM are based on the observation that certain attention scores are often higher than others. Sliding window is based on the intrinsic structure of languages, where each token is typically more correlated to the previous few tokens. Therefore, for each query we only take into account the contributions of the keys that positionally close to it. The StreamingI.IMM framework is motivated by the observation that autoregressive LLMs have a surprisingly large amount of attention score concentrated the initial tokens, and thus each query only takes into account keys that are positionally close to it, as well as the first few (usually 3 ~ 5) keys, which are called "attention sinks".
We show that both cases we can use linear number of small transformer oracle calls to simulate them, even in the worst case. As summarized below, result indicates that oracles capture efficient attention based on sliding windows and attention sinks efficiently.
Theorem 1.4 (Theorem 5.1). For any transformer T with layers. H attention heads in each layer, imput length N, embedding dimension d, constant-size sliding window, there exists an algorithm that simulates T with O N HL calls to a transformer oracle with L' layers, H' attention heads in each layer, input length M and embedding dimension O dH' with causal masking. This result H
M H'L')
still holds if we have constant-size attention sinks.
1.3 Related Work
Representational strength and limitations of transformers. The representational strength of transformers has been intensively studied in recent years from a variety of perspectives. To list few, (MSS22] MS23 SMW+24] study the class of problems that transformers can solve from a
Hah20 aim understand whether transformers can recognize formal languages; SHT23 focus on reasoning tasks and show that transformers are inherently capable of solving sparse averaging: SST24 gives important connections between transformers and the massively parallel computation model; [SSK+25 HWI. +24 uses computational complexity to characterize the computational limits of diffusion transformers and low-rank adaptation for transformers; [I.CW23 studies attention's 's capability of approximating sparse matrices; [Y YCB+20) shows that transformers and many subquadratic variants are universal approximators for scquence-to-sequence functions;
circuit complexity viewpoint; [BAG20 LAG 23
Fast attention mechanisms. There has been a fruitful literature of dealing with long input se- quence by designing "subquadratic alternatives" to transformers, which are variants on the attention mechanism which can be performed subquadratic time. For example, researchers have studied various sparse attention mechanisms that only consider the query-key pairs that have high correlation,

---

including Reformer [KKL20] Longformer [BPC20] and Hyperattention [HJK 24). Additionally, there has been work on kernel/low-ran attention that approximates attention mechanism using kernels such as Performer (CLD 21] and Polysketchformer [MZ224] and there has been growing interest in state space models such as Mamba [GDD23] See [TBB222 for a comprehensive survey on efficient attention mechanisms. However, [AY25] proves that none of these subquadratic models can capture all pairwise correlations even approximately as the sequence length grows.
Preliminaries
2.1 Transformers
We first define the standard attention mechanism in Transformer.
Definition 2.1 (Attention Mechanism). Given input X E RNxd, query, key, value matrices Wº, WK WV Rdxm, the attention mechanism computes
Att (xtTnx((((W))////))))))) RNN..
Here we say N is the context length, and d is the embedding dimension. We will also call each attention mechanism an attention head in the transformer architecture. For notational convenience, we let
(q....,qu E Rmm (ki...., kN} E RRm (ui,..., uN E R.
be the rows of XWQ,XW' xw* XWW respectively. We will call them the queries, keys and values. As result, the attention mechanism is computing
exp((a,;k))) U/
Σ5nr exp( k;))
for each query Qi-
Another important component in transformers is the multilayer perceptron (MLP). An MLP is feed-forward, fully-connected neural network consisting of one or more hidden layers using ReLU activation. The universal approximation theorem states that any continuous function with a finite support can be approximated by a neural network with one hidden layer [HSW89]. In light of this, in many relevant works [SHT23 SHT24) MLPs modeled as arbitrary functions compact domains.
In this paper, our goal is to use small transformers to simulate large transformers, and we would like ensure that the MIPs the small transformers are as simple as possible. We will therefore assume that MLPs in small transformers compute functions Rdd R(() such that:
1. They are at least strong the MLPs in the large transformers, i.c. they can do whatever computation that MLPs the large transformers can do, and
2. They can do basic arithmetic operations on the input vector æ E Rd or pad fixed numbers to it (both are simple continuous functions) as long as they take ( time.
When MLP @ is applied on a matrix, will be applied row-wise to output another matrix. other words, it is applied on each token given sequence of tokens.
An attention layer ff with attention heads consists of H attention mechanisms with query embed- ding W W.K. WV TR mm for the h-th attention such that m = ' The input X is partitioned into H matrices X[: Di],
X[: DHI ..l.D.....f.......... R column-wise where D:
{ ((-1)) 1...,, id
for all i, such that the h-th attention head computes
voftmax((X]: D., D.,,, (X]: ()X), Nxm.
All attention outputs are concatenated column-wise and fed through layer MLP & such that the output of attention layer f is
f(X) = - (ox,tma D.JWY) D.JKK) E Nxd
5

---

Definition 2.2 (Transformer). A transformer T with L layers and H attention heads in each layer consists of an input MLP Φ R2d + TRd applied token-wise on the input X E Ng L attention layers f1...., R - R Nxd which contain layer MLPs th....., R applied token-wise at the end of each attention layer. For each 2 S sesL.
x 4 (f (e(ff((((-11))
Finally, the transformer T outputs T(X) x
We will simplify the notion of positional encoding into input MLP Φ and assume that the input MLP has positional information of the tokens. In other words, x2 X(i, is the i-th input token, then (xx;) is also function of i.
Transformer is powerful as computational model, and we refer the readers Appendix A for more operations that transformers can do that will be useful in our proofs.
Transformer Oracle. A transformer oracle O is small transformer that can only take inputs of length at most . (its embedding dimension, number of layers, number of heads in each layer, causal masking etc will be specified in result statements). In this paper we are mostly concerned with simulating transformers with large input length N using transformer oracles with input length M such that M < N (recall that assume Sloog N) s M < o(N)).
2.2 Causal masking, sliding window and StreamingLLMM
We first define the most commonly used causal masking in attention heads.
Definition 2.3 (Causal Masking Attention). Given input X E Rxd, query. key, value matrices W WK WV E Rdxmm the attention mechanism with causal masking computes
(t) softmax (m=s((XXW))XXXX))) (XWV) RRN
where the mask function sets all upper triangular entries (not including diagonal entries) to cc.
Another commonly used masking scheme for efficient transformer inference/training is sliding window, where only keep the keys whose indices are close the query index.
Definition 2.4 (Sliding Window Attention). Given input X E Nxd query, key, value matrices Wº, WK WV E Rdxm and window size 2 1, the attention mechanism with sliding window of size r computes
AXt softmax (windoww(XWW)))WWW)))) (XWV) e Nxm.
where the window function sets all entries in ((i,j) : i or S r 1o xc
In other words, for each query we only look at k, such that i- +sj i.
Finally, StreamingI.LM XTCC+24 is framework designed for efficient training with finite length window. Upon having fixed-size sliding window, each query also attends to the first keys (called "attention sinks"), where is usually a small positive constant (around 3 5).
Definition 2.5 (Attention Sink). Given input X Nxd query, key, value matrices Wº, WK WV E Rdxx and window size r 1, sink size s 2 1, the attention mechanism with attention sink computes
Attn(X) softmax (sink((W))(XXW) ((n (XW>) E Nxm
where the sink function sets all entries in (i..) :j ior < Sjsi-r] to -00.
Transformers with causal masking attention, sliding window, and Streamingl. LMM are defined exactly the same as transformers except that we replace standard attention mechanisms by attention with causal masking, attention with sliding window and attention with sinks.

---

1 instance of Transformer
HL instances of Transformer
Input length N
Input length N
L layers
layers
H attention heads in each layer
attention heads in each layer
Embedding dimension d
Embedding dimension
Lemma 3.1
Corollary 3.2
N-HL MCHLL
H M2
instances of Transformer
instances of Transformer
Lemma 3.3
Input length M
Input length M
L' lalayers
layers
H' attention heads in each layer
attention heads in each layer
Embedding dimension L(HH)
Embedding dimension O(d/H)
Figure 1: Proof Roadmap
2.3 Notation
Throughout the paper, we denote X Nxd as the input to the large transformer, where N the input length and d is the embedding dimension. For N x d matrix X, we use X[t, denote its i-th row, X J. to denote its j-th column, and X [ to denote its (i,j)-th entry. Given sets S S [N],
[d]. we use [[S to denote the submatrix consisting of the rows in S, X D to denote the submatrix consisting of the columns in D, and ([S, D] to denote the submatrix consisting of the entries in D of X.
We use WQ, K W to denote the query, key and value matrices for attention heads, and we use qs ka, Us to denote the i-th of XWQ, XWK XXW respectively. We also let S; {(t 1)M 1, tM) for all < < N/M.
We use lxb to denote the x matrix whose entries are all 1, and 0axb to denote the a x matrix whose entries are all
We now turn to proving our results. We give proof sketches and main ideas here; full proofs are deferred the appendix.
Quadratic calls suffice for simulation
H" small transformers with I,' layers and H' attention heads in each layer suffice to simulate a large transformer with T. layers and H attention heads in each layer (Theorem 3.4). Our proof roadmap is illustrated in Figure [ where the arrows A - B indicate that can be simulated by B. Complete proofs of all the statements can be found in Appendix B We first show that this is the case when they both only have single attention head, i.c H'= -
In this section, we prove that O(( 2 HL
Lemma 3.1. any single layer, single head transformer with input length N, embedding dimension d, there exists an algorithm that simulates T with O M2) calls to a transformer oracle with input length M and embedding dimension (d).
Proof Sketch. Our high-level idea to partition the x N attention matrix of T into M blocks of size M M, and then constant number of oracles separately handle each block. In particular, each block corresponds to two sub-intervals of length M out of the input sequence of length (one interval for the oracle for sequence length ((M) compute the contribution of each block. To be more precise, as in Definition 2.1 above, let
queries, and one interval for the columns, or keys),
aim to have
{q....., AN E RT (ki.... ..... kN} 1. (UI....,,N E T
7

---

be the rows of XWe, xWW K XWV respectively. Define
a = exp((g;,k)) ky)), and bi. = exp ky)) vy.
The goal of the attention mechanism is to compute, for all i,
N
سزر bij
N/M Ejes,
bis
expl kz)) v/
1=1
Σ5 exp((a, kz)) j=1
Σj=1 dN.j
N/M
Ejes, a.j
The main technical difficulty is that one oracle call not able to give us information on the sum of ai,j (or ba.)) over all E [N] However, we show that one oracle call allows us to compute Ejes. "ij where S, [(t - 1)M + 1,.... +M} such that N/M oracle calls suffice to give us -i== Dz We do this by adding in one synthetic token to the sequence so that its contribution is fixed. i.c. its inner product with all the keys will be the same and known. In addition, we assign its corresponding value token to be O and other value tokens to be 1 such that the output does not contain the synthetic token's ' value, while the normalizing term still counts its contribution. As result, the output of the oracle will give us
Ejes, Dij
Ejes, 0ily +
where is the attention value (that set and thus know in advance) for the normalizing term. This information allows us to compute EjEs, ai as we can solve a linear equation using MLP. Secondly, will directly feed the oracle with [],, W W WV obtain
Σ Ejes, bi.5 Ejes, Dijj
and since we already know Ejes, Oz.j. we can compute Ejes, ds.g, which will furthermore give us Σ/=1 bag by summing them up.
We now move on to generalizing Lemma 3.1 to general H, I., H', I', L i.e., when the transformer T and the oracles can have multiple heads and layers. A first attempt to do this might use different layers of to simulate different layers T, but this appears difficult to implement, since Lemmaß.] requires some processing between layers of attentions that is not available to when the different layers are connected only through MLPs within an oracle. Indeed, since the output of each attention head needs processing before it can be used in another attention head, it is unclear how to take advantage of more than one layer of each oracle in this way. We instead take a different approach: we all the attention heads in all the layers of the oracle completely independently from each other to simultaneously simulate O (H'L') different attention heads, and we use these all together to simulate one layer a time of T.
First, it is not hard to generalize Lemma 3.1 to general H, T. (but still H' = T/ 1) by separately simulating each attention head in T regardless of which layer it is in:
Corollary 3.2. For any transformer T with L layers, H attention heads in each layer. input length N, embedding dimension d, there exists an algorithm that simulates TT with O({ N )2. HT) calls to a single head, single layer transformer oracle with input length M and embedding dimension O (44)
Next we show that transformer with L' layers, H' attention heads in each layer, input length M, and embedding dimension O dH'L''
H = ) can be used simulate H'L' instances of single head, single layer transformers with input length M and embedding dimension f!- In other words, we are able to independently use each attention head in the transformer, regardless of which of the T,' layers appears in:
Lemma 3.3. One transformer with L' layers, H' attention heads in each layer, input length M and embedding dimension O 2H'L) can be used to simulate H''L independent instances of single layer, single head transformers with input length M and embedding dimension 4
Proof Sketch. Consider first when L' = 1. A transformer with H' attention heads naturally parti- tions (by definition) the embedding dimension O dH' H into H' parts of size O d ). and each head
8

---

separately computes an attention mechanism on one of those parts. The result follows almost directly. with some care to details about MLPs and aggregation.
More care is needed when L' 1. We partition the O L coordinates of the embedding
H each, and the key idea is that each layer will operate on one of those parts while leaving the rest unchanged. Indeed, weights for the query and keys can be selected so that only the relevant part of the coordinates will impact the attention matrices at each layer, then weights for the values can be selected so that the other parts are passed through the layer without being changed.
dimension into T.' parts of size ( dH'
Finally, we combine Lemma 3.1 Corollary 3.2 and Lemma 3.3 to obtain our main result.
Theorem 3.4. For any transformer T with L layers. H attention heads in each layer. input length N. embedding dimension d, there exists an algorithum that simulates T with O{{ (M) )2 H'E.) calls to transformer oracle with T' layers, H' attention heads in each layer, input length M, embedding dimension O O(HH'L" 1
We additionally show that these results still hold when both the large and small transformers have causal masking. The proof's are similar to the proof of Theorem 3.4 and are deferred to Appendix B Theorem 3.5. For any transformer 'T with layers, attention heads in each layer, imput length N. embedding dimension d and causal masking, there exists an algorithm that simulates 'T with C )2 #FT) calls to a transformer oracle with L' layers, H' attention heads in each layer, input length M, embedding dimension O dH'L') and causal masking. H-
4 Efficient simulation with average-case input assumptions
4.1 Linear calls suffice for average-case inputs
In this section we prove that if the queries, keys and values in the attention heads are somewhat bounded in how much they may differ from each other, then O N small transformers suffice to approximate large transformer. We provide a proof sketch below, and the complete proof can be found in Appendix C.I]
Theorem 4.1. Let T be a transformer with L layers, H attention heads in each layer, imput length N and embedding dimension d. Suppose there exist absolute constants C, D > such that
N Σ j=1
C S an C, and DN max [|b,,il2 S
bis
J
2
where
04.j = exp(((i: kz)), exp( (gi, kj)) Uj
for any query qs, qi,kj, Vj in any attention head. There exists an algorithm using O O HL
HP oracle
calls to small transformer with L' layers, H' attention heads in each layer, embedding dimension
O dH' L' obtain an E1+ approximation of T with probability at least 0.9 for any fixed constant
E O.
Proof Sketch. The high-level idea is to partition the queries into N/M parts of size M each, and then permute the keys (but not the queries) using a random permutation T. We then aim to ap- proximate the desired quantities Σj=1 exp( k2)) and Σn= ex,((g, kz)) By using rescalings of Ejes, exp( (q,, k-)))) and Ejes, exp( (q., k=G))) Ur(z) (where S, is the part of size M that contains query q.). This can be seen as estimating the desired sums by sampling only M of the N summands at random. At the same time, by blocking the queries and keys like this, the samples can
be computed using oracle calls similar to Lemma 3.1 above.
4.2 Linear small transformers are weaker than large transformers
We also show that N/M small transformers can be simulated by a large transformer along with an oracle for performing very small matrix multiplications (M with d x d). We only prove the statement for single head transformers to illustrate the need for linear amount of oracle calls.

---

Theorem 4.2. Given N/M instances of single layer. single head transformers with input length M and embedding dimension d, there exists an algorithm that simulates them with one call of a single layer, single head transformer with input length ( and embedding dimension (dd), along with O(N/M) many matrix multiplications of size M d x d.
The key idea behind Theorem 4.2 to concatenate the tokens from all N/M input sequenees into single long sequence of length N, but then slightly increase the embedding dimension a way which makes tokens from different short sequences highly uncorrelated with each other. Thus, the large attention will not give much weight to pairs of tokens from different short sequences. The complete proof is delayed to Appendix C.2
5 Simulation of transformers with sliding window and StreamingLLMMs
In our last section, we show that small transformers work well when we add sliding window masking attention heads, and when in the StreamingLLMM framework. Our constructions are similar to above, but with additional techniques to take advantage of the masking structures, and can be found in the Appendix D
When we consider sliding window attention, we only need to deal with keys that are close to each query. is intuitive can be covered with a M x M block matrix, which can be computed using our oracle. Transformers with attention sink is similar transformers with sliding window, except that have extra "sink window" in the beginning for all the queries. These sinks windows can be computed using O ( oracle calls.
that in such scenario, the attention scores of consecutive M queries
Theorem 5.1. For any transformer T with L layers, H attention heads in each layer, input length N, embedding dimension d, constant-size sliding window, there exists an algorithm that simulates T with O Mr #4,) calls transformer oracle with L' layers, H' attention heads in each layer, input length M and embedding dimension O (d' with causal masking. This result still holds if have constant-sic size attention sink.
H
10

---

6 Acknowledgments
We thank Daniel Hsu, Jingwen Liu and Vatsal Sharan for useful discussions.
References
[4ET+24) 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.
[AS24] Josh Alman and Zhao Song. Fast attention requires bounded entries. In Proceedings the 37th International Conference Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc.
[AY25] Josh Alman and Hantao Yu. Fundamental limitations on subquadratic alternatives to transformers. In The Thirteenth International Conference on Learning Representations, 2025.
[BAG20] Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal, On the Ability and Limitations of Transformers to Recognize Formal Languages. 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 Computational Linguistics.
[BHBK24] Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the representational capabilities of transformers and recurrent architectures. In The Thirty-eigtth Annual Conference on Neural Information Processing Systems, 2024.
[BPC20] Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv:200..05150, 2020.
[2]F+22) Ilias Chalkidis, Xiang Dai, Manos Fergadiotis, Prodromos Malakasiotis, and Desmond Elliott. An exploration of hicrarchical attention transformers for efficient long document classification, 2022.
[CLD*21] Krzysztof Marcin Choromanski, Valerii Likhosherstov. David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter Hawkins, Jared Quincy Davis, Afroz Mohiud- din, Lukasz Kaiser, David Benjamin Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[CMS+20] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kir- illov, and Sergey Zagoruyko. End-to-end object detection with transformers. In Com- puter Vision ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part I, page 213-229, Berlin, Heidelberg, 2020. Springer-Verlag.
[Dee21] Google DeepMind. Scaling language models: Methods, analysis & insights from training gopher. CoRR, abs/2112.1 1446, 2021.
[2F Tri Dao, Daniel Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: fast and memory-efficient exact attention with io-awareness. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS 222 Red Hook, NY, USA, 2022, Curran Associates Inc
[Etc24] Etched. Etched is Making the Biggest Bet in AI. bttps://www.ethhhe com/ announcing etched, June 2024. Accessed on October 18, 2025.
[GD23] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00755 2023.

---

[Hah20] Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156-171, 2020.
[4] Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David Woodruff, and Amir Zandieh. Hyperattention: Long-contess attention in lenerr time. In The Twelfth International Conference on Learning Representations, 2024.
[55 Jerry Yao-Chieh Hu, Maojiang Su, En-Jui Kuo, Zhao Song, and Han Liu. Computa- tional limits of low-rank adaptation (loRA) fine-tuning for transformer models. In The Thirteenth International Conference on Learning Representations, 2025.
[HSW89]
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward net- works are universal approximators. Neural Networks, 2(5):359-366, 1989.
[HWL+24] 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.
[JBKM24) 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 st International Conference on Machine Learning, ICML'24, JMLR.org, 2024.
[KDW+21] 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 scale. 2021.
[Kim24] Hanjoon Kim. RNGD preview: The world's most efficient AI chip for LLM infer- ht//bbog//mggt-preiiew--t--t
ence. https: pettps:/ffurie http://frrosaaa..ee on October 18, 2025.
2024. Accessed
[KKL20] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient trans- former. In 8th International Conference Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[KMZ24] Praneeth Kacham, Vahab Mirrokni, and Peilin Zhong. Polysketchformer: fast trans- formers via sketching polynomial kernels. In Proceedings of the 41st International Conference on Machine Learning, ICML' 22. JMLR.org, 2024.
[L3G+23] 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.
[LCW23] Valerii Likhosherstov, Krzysztof Choromanski, and Adrian Weller. On the expressive flexibility of self-attention matrices. Proceedings of the AAAI Conference on Artificial Intelligence, 37(():8773-8) Jun. 2023.
[LL19] Yang Liu and Mirella Lapata. Hierarchical transformers for rization. In Anna Korhonen, David Traum, and Lluís Mårquez, editors, Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5070-5081, Florence, Italy, July 2019. Association for Computational Linguistics.
summa-
[MS23] William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log- precision transformers. Transactions of the Association for Computational Linguistics, 1 11:531-545, 2023.
[MSS22] 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.
[Ope20] OpenAl. Language models are few-shot learners. In Proceedings of the 34th Interna- tional Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc
12

---

[PZV 19] Raghavendra Pappagari, Piotr Zelasko, Jesús Villalba, Yishay Carmiel, and Najim Dehak. Hicrarchical transformers for long document classification, pages 838-844, 12 2019.
[SHT23] Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational strengths and limitations transformers. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2023. Curran Associates Inc.
[SHT24] Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic depth. In Forty-first International Conference Machine Learning, ICML 2024, Vienna, Austria, July 2 21-27, 2024. OpenReview.net, 2024.
[SMW+24] Lena Strobl, William Merrill, Gail Weiss, David Chiang, and Dana Angluin. What formal languages can transformers express? survey. Transactions of the Association for Computational Linguistics, 12:543-561 2024.
[TDBM22] Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey, ACM Comput. Surv., 55(6), December 2022.
[VPSP23] Ali Vardasbi Telmo Pessoa Pires*, Robin M. Schmidt, and Stephan Peitz. State spaces aren't 't enough: Machine translation needs attention. In EAMT, 2023.
[VSP+17] 17] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, tukasz 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 Hook, NY, USA, 2017. Curran Associates Inc.
[WDL25] Kaiyue Wen, Xingyu Dang, and Kaifeng Lyu. RNNs are not transformers (yet): The key bottleneck on in-context retrieval. In The Thirteenth International Conference on Learning Representations, 2025.
[WXQ+21] Xiaohui Wang, Ying Xiong, Xian Qian, Yang Wei, Lei Li, and Mingxuan Wang. Light- seq2: Accelerated training for transformer based models on gpus. arXiv preprint 1r.:5:2110.05722. 2021.
[4] 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.
[YBR+20] Chulhee Yun, Srinadh Bhojanapalli,, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transformers universal approximators of sruuence-to-seqeece functions? International Conference Learning Representations, 2020.
[YCB+20) Chulhee Yun, Gin Chang, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J.
Reddi, and Sanjiv Kumar. O(n) connections are expressive enough: Universal approx- imability of sparse transformers. NeurlPS, 2020.
13

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Abstract highlights this paper's main results and motivations.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Even though the motivation comes from practice, this paper is purely theo- retical. It mentions that the goal is to provide a theoretical framework for possible future empirical followups.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification:
All the model assumptions clearly stated in introduction section.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This is purely theoretical paper with experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This is purely theoretical paper with no experiment.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ ccipps.c/puulli//guu /otee//guuddde/eooSuuubbmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is purely theoretical paper with no experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is purely theoretical paper with no experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This is purely theoretical paper with no experiment.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:://///aarpppscpccppptt///ta
Answer: [Yes]
Justification: This paper does not have harmful content and only has theoretical analysis and proofs.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
The authors are unaware of any possible societal impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is purely theoretical paper with no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: This paper mentions related work to the best knowledge of the authors.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
18

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This is purely theoretical paper with new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This is purely theoretical paper with no use of human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This is purely theoretical paper with no crowdsourcing or human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
19

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method of this paper does not use LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neur/a: 2 for what should or should not be described.
20

---

A Transformers as Basic Functions
We show that single layer, single head transformer (attention mechanism with MLPs) act as few different basic functions on the input matrix X that we will need later.
First we show that can turn any matrix X into matrix that is consisted of block matrix of ones and zeros everywhere else.
Lemma A.I. There exists a fixed matrix U E [ed+11xdd and input MLP & Rd + Rd++1 such that for any input X E R RNxx
o(X)U = 1axb -10000 0)
for any N,b b S d.
Proof. Let T; = X =] for all E [N]. Define x(x;) = ( 1) if s a and o(x,) = (x,, 0) i 1.+1111 Let
(0xx Odx(d-b) U
11x6
Oax (d-b)
is straightforward to check that o(X)U is the matrix desired.
Using this, we can construct transformer that computes the sum of all input tokens. Lemma A.2. There exists single layer, single head transformer with embedding dimension d such that, on input matrix X Nxd, it computes Σ X(t, :] E R1xd
Proof. By Lemma A.1 there exists WQ, W such that (XW9) = (t,*) = 1ixd and k; N [ for all s S N. As result, the output for any token will exactly be E
A single layer, single head transformer also allows us to construct look-up table such that each token can find information from other tokens.
Lemma A.3 (Lemma D.1 of [SHT24]). Given input matrix X E R indexing function Rdd x [N] and f I + T there exists a single layer, single head transformer with embedding dimension d such that the i-th output is p(X)
B Missing Proofs in Section
Lemma B.1 (Lemma For any single layer, single head transformer with input length N, embedding dimension d, there exists an algorithm that simulates T with O N² oracle with input length M and embedding dimension (d))
calls to a transformer M2
Proof. Let T be any single layer, single head transformer with query, key, value matrices W WK WV Rdxd with arbitrary input X I Nxd Let B be upper bound of the ab- solute value of all entries in X, Wº, W WV Without loss of generality we can assume the first MLP & is the identity function because otherwise we will compose it with the input MLP in the oracles. In addition, we can also assume that the layer MLP is the identity function, and this is because if not, we can first set the layer MLP in our oracle to the identity function compute the output of the large transformer before the layer MLP, and then use ( oracles as layer MLP to compute the final output.
Define (as usual) Q = XW K K = XWV and qi = :]i = :l.,;,, = Vii < < N, and let S. = ( (1- 1)M, ...., LMJ for all S < 37
Our goal to simulate
(oftmax(g:KT)) Σ exp((g, k;)) 2y
Σn bis
N/M Bie
(1)
Σj exp kj))
Σラ Oi.i
E
NjM
Act
for all 1 1 N, where we define
ai exp((gi k2)), b,s == exp((gr,
21

---

and A= ExEs, ai and B = EjEs, b... Our algorithm can be summarized as the following two steps:
1. (Step 1) We calculate Ar, for all < N, S N/M using (M) oracle calls.
2. (Step 2) For each i, we exactly compute Aga for all i E [M] using N oracle calls. Since we already know A3, for all i, 1, we can now compute
ENM BEd ΣN/M Ar,
Σ
Bud Asat
Are
ΣN/
Ar,
for all i. Notice that this can be done either trivially or with O(( oracle calls with Lemma A.2 A.2 and the fact that we allow MLPs to do division.
Step 1: Calculating A,, for all i, t. We first consider the case when E S.. For any S t S define
N
M
W
WQ 0
9) w
(0 1 E R(d+1)x(0+2)
(WK
and MLP ó such that
9(t 1)M-1
Q' = ((((s.:) -W'' -
[]
1Mx1] )xx))
( (WQ
(xx1)
01xd
1
Oixd
G&M
0
k(1-1)M+1
x[Str:]
larxi) ) (
Oax1
K' =(([S);) WK'
01xd
OIxd
1
KeM
(1xxd 01xd
0xx1 0
V'
We construct V and add extra dimension using MLP such that obtain V using Lemma A.1 but we omit it for simplicity. In particular, we will only need to use the first column of V so for We keep our notation consistent and
what follows below, V' could be (I,..., 1, IR (M++)xx1 let it have d + columns.) Therefore, we have
+1
(ge-n)+ K(M) +
1
T'(K'=== =
(gess K(M) +
Finally, we can calculate that the entries of (o"") are given by
Ejes, exp( (qi, ky) + 1) Ejes, exp((g. k2) + 1) + exp(1) Ejes, or + exp(0) A + exp(0)
EjEs, 04,
A
for all i E Sr. Therefore, we can use the MLP layer to calculate Air as:
A cxp(0) A,
A
A,, A..
Now we compute Ar, when i E Sp for some t' # The high-level idea is similar, but now we feed the oracle with [X[S X[Sy, E R x2d and we let the MLP be such that
!) ((M+1)x(24+1)
x =
0 01xd
Oxxd
22

---

and we furthermore define
Oaxd W
Odx1
W
Oax1
wen
.Wk"
(2(22+1)x((+1)))
Odx1
Odxd
Oax1
01xd
lixd/
01xd
lixd
such that
1(0 11M++1
Q" [x W0-
inii
R (((+1)x(441)
1
01xd
((0-1)M+1
K" ==
wk"
R (M++)x((+D))
KIM
01xd
V"
1axx Olxd
0xx1
R((++)x((+1),
0
Therefore, we have
(q () +
T=
(geM, B(s- R(--)) +1
Mg heas) +
We can now compute Ai, for all E Sy for the exact same reason as above. Step I requires ( )a oracle calls.
Step 2: Computing
Bi, using oracle call simply by A,, B.s for all i Sp where feeding the oracle with x[S WQ. W WV remains to compute Ar,
Bat for all i, If E S₁, can compute Aia
f t. We feed the oracle with [X[S, [ :]] and let
(Oaxd W
W 0dxd
WV Odxd
R 2ddd
such that
a(0 1)M++1
Q" X[S,. we"
ge
k(1-1)M+1
R" X[5,s] Wk"
KEM
1(t-1)M41
V"V X[S,:]) WV"
VeM
B. for i E Sy. In total need A simple calculation shows that softmax (K"" gives A.t
N. M oracle calls in step 2.
Corollary B.2 (Corollary 3.2 For any transformer T with L layers, H attention heads in each
layer, input length N, embedding dimension d, there exists an algorithm that simulates T with O(( 3. L) calls to single head, single layer transformer oracle with input length M and embedding dimension O d.
23

---

Proof. We simply compute T layer by layer and head by head. For each layer, we compute the output of each attention head, which requires O(( 37 H)) oracle calls using Lemma B.1 concatenate and repeat for each layer.
Lemma B.3 (Lemma 3.3 One transformer with L' layers, H' attention heads in each layer, imput length M and embedding dimension O ((=MT/²) can used to simulate H' independent instances of single layer, single head transformers with imput length M and embedding dimension d H
Proof. Given H'L independent instances, we label the instances by (h, () E Hl'I'x x L' and concatenate
them together by columns to X E R RMx awct! such that
X1,
X2.............. , XHr.
where Xa.e is the input of the (h, f)-th instance for h E [A'),E [T']. As result, in the first layer,
(K,, X., RMx " is sent to attention head h. Let W w WV R xRxx3 denote the query, key and value matrices in the (h, 1)-th instance. We construct W W W.V as
WQ
WK
WV
0
we
# x
WK
#1
WV
x
0 A x
x
and layer MIP the same the layer MLP in instance (h, 1) such that attention head h in layer 1 exactly computes the (h, 1)-th instance. Also observe that we are not performing any computation regarding (h, f) instance for any l /f The same argument holds for all h, and therefore layer one of the large transformer computes (h, 1)-th instance for all 1 < h < H'. Since the outputs of all H' attention heads are stored at predefined locations after each layer, we can repeat this process for L' times to compute all instances.
Theorem B.4 (Theorem 3.4). For any transformer T with L layers, H attention heads in each layer, input length N. embedding dimension d, there exists algorithm that simulates TT with O(( MM 12 HL calls transformer oracle with L' layers, H' attention heads in each layer, input #t)
length M, embedding dimension O dH'L') H
Proof. This follows from Corollary B.2 and Lemma B.3
Theorem B.5 (Theorem 3.5). For any transformer' T with L layers, H attention heads in each layer, input length N, embedding dimension d and causal masking, there exists an algorithm that simulates ' with N) 32. WHt) calls to a transformer oracle with Lt layers, H' attention heads in each layer, input length M, embedding dimension O I and causal masking.
The high-level idea is identical Theorem B.4
We first show that single layer, single head transformer with input length M and causal masking can compute Ej=1 exp((a; k2)) for all 1 s i < M given input and all parameters.
Claim B.6. Given any E Mx WQ, WK WV E Rdxdd one calls to a single layer, single head transformer oracle O with input length M, embedding dimension (dd) and causal masking suffices compute Ej=1 exp(/gs kg)) for all < i M.
Proof. We define
( IWQ O1xd)
(W 01xd) 0xx1
W
I ( .wk
1 {d) ((++))((++1
0xx1

---

such that
0
x'==((X) w - =
(Oxxe
(1xd X
(we 0ax1
01xd
qi
E (2(++1)x(d1))
1xx1
:
9Ms
1
K' ((X) Wk'
-Oxe X
01xd
lasx1 )
1
01xd)
k1
1
([(++)x((+1)
0dx1
1
KM
V' OmxI 1xxd)
01xd
E (
As result, we have
1 (m), (q1, ki)
1
kws)
Q'(K')-
:
(gas k1)
{a kad))
Finally, we can calculate that the (i, entry (oltmax(mas((""KA V) (K)''))''' is Σj exp((( kj) 11) Ej=1 exp( kj) 1) + exp(1)
M + 1) of the oracle output,
Σ 0
Σ Ej=1 11-1 + (x)
Finally, we can define the MLP such that it outputs
Σi=l ب11ي
exp(0)
0:-15
Σ 91-1. +0
for all 2 1.
First notice that Lemma B.3 still holds if we add causal masking to the transformers because the proof is not affected by causal masking. In addition, the analog of Corollary B.2 will hold even if we add causal masking to the transformers if we can show that Lemma B. holds under causal masking since the proof is the same. Thereeooe, it suffices to prove Lemma B.I under causal masking.
Proof of Theorem B.5 The proof is similar to the proof of Theorem B.4
Let T be any single layer, single head transformer with query, key, value matrices Wº, W WV E Rdxd and causal masking, with arbitrary input X E R. For the same reason as Lemma B. we assume without loss of generality that both the input MLP and layer MLP are identity functions, and we use the same notation as in Lemma B.T
Our goal is to approximate
E exp((n kz)) 133
Ejmbis bis
E exp((q: ky))
Σ aij
for all <i < Notice that we already include causal masking in this expression by only summing over j Define
100
Σ
(2) 21
= Σ
aij = Ar, = A! + A!
jESiN(i]
JES [t]
and
B
Σ
big B
byt + B = B + (2)
it
JES
JES.-[8]
For each i E St, we want to compute
B(1) 1e
(2 A
(1)
Σ1 BEd + (1)
Σ+1 Ai,t' + 112)
Σ (A
(1) + A + 11)
25

---

8 _ A,, A0 A
Just like Lemma B.1 we will compute A
with our oracle independently for all
1s1's (each with oracle call). In addition, A
can be computed with single oracle call
B
A can be computed using a single oracle call by simply feeding the oracle with X[S,, W W W.
using Claim B.6 and
(
To compute A/ and with one oracle each for all i, f', we can use the exact same construction '.
in step 1 in the proof of Lemma B.1 (this works because our oracle also has causal masking). To
B(a)
compute A/ and A
first define such that
J&M
Oxx 2PM
JEM-1
6 (X(ss.))
()--) O1xd
1)M-1
T(y-1)M+1
Notice that this valid because & has information on the position of all the tokens. Furthermore, Lemma A.3 allows oracle to perform this computation well. We also let
W =
W 0dxd
W.
(Odxd
WK
such that
9&M
9tM-1
Q' = X| -
4 11-1) 01xd
01xd kv M
K' (), WK'
k(--1)M+1
01xd
O
V'
LMxd OMxI)
Now notice that
(qeM, RrM
(ges, kie- -1)-41) (9-M-1, Ki 1140++1)
(1eM-1, 1, kr
Q(K')T=
0
(1: 1)M41, kym)
(a(--1)441, kie
10
Therefore, the (tM - + 1)-th row of softmax (matmax(mmss(((( (ana)(""("K which corresponds to 9is is computing
EN' exp( ky))
Σj=it exp (q:, ky)) exp(
n2 A/
which allows us to compute
E exp((gi kg)) = A exactly. Furthermore,
2 can be S
computed by letting
Wº""
WQQ 0axd
w-K"
(ddxd WK)
..VV ((dxd) M.V
26

---

such that
9.M Q&M -1
Q" = ox w
A(t 1)M+1
KyM ke M-1
K" = 6 X wK"
1)M+1)
U
MMM-1 V
:
1(M-1)M+1
In total we need O(( N )²) oracle calls, and the proof is complete.
Missing Proofs in Section
C.1 Missing Proofs in Section 4.1
Theorem C.1 (Theorem 4.1). Let be a transformer with L layers, attention heads in each layer, input length N and embedding dimension d. Suppose there exist absolute constants C, D > 0 such that
N
C S abd S SC, and DN max lbb l2
S
bid
where
0. exp((gi, b.. exp((gi, ky))
HL for any query qs, Ki, in any attention head. There exists an algorithm using O O HE oracle calls to small transformer with L' layers, H' attention heads in each layer, embedding dimension 0 AH' to obtain an (1++) approximation T with probability at least 0.9, for any fixed constant
Proof. By Corollary B.2 and Lemma B.3 it suffices to prove the Theorem with H = I. = because when we generalize, all the attention head computation will be in parallel with each other.
Let T be any attention head with query, key, value matrices Wº W W E 12dx with arbitrary Without loss of generality
assume the first MLP á is the identity function because otherwise we will compose our oracle MLP with ø. In addition, we can also assume that layer MLP is the identity function, and this is because if not, oracle layer MLPs to compute the output of the large transformer before the layer MLP, and then use O( oracles as MLP to compute the final output.
input X E RN RNNx
still use identity functions in
Define Q XW9, K XW V XWV such that qi Qli :] K(i,;), Vi for all N
1 1 i < N, and let S. ((1 1)M, ...,, LM} for all S S1 < M7
Our goal is to approximate
softmax KTV Σ/- exp( (qi, k2)) Dj
j= bij
ΣS exp( (q:, k;))
Σ Oi
for all 1 < iiiSA N. The algorithm will be divided into two parts like before.
Step 1: Approximating Σ/= as for all < N. Let S, for some 1 1st5 N. We pick random permutation of [N), and by Lemma A.3 we can use O(N/M) oracle call (one for each
In practice, one would likely perform this permutation directly rather than using oracle calls, such as using the pytorch utility randperm. However, since it is negligible additional number of calls, we use oracle calls here to simplify the computational model.
27

---

[ :)) to map 2; to (r,))=()) for all 1 sis N. Now we use the first MLP Φ in the oracles to map to
[ 01xd
X(T(S)), 01xd
1
=
and we furthermore define
WQ Oaxd
Dax1
Odxe W
Odx1 0ax1 1
w
Oax1
.kkk
01xd
1
01xd
in the oracle such that
1)t-1)4+4
Q' = x((x)
E 12(++1)x(++1)
QUM
1
(((((-1)M+11)
((((s)) := (X ((
E R (d+1)
kT((M)
V' -Iarrd
MMxd Lax1
0mx1
1
N Now we can compute Ejes, (j,(() for all using same as the proof of Lemma 3.1) Our estimator of ΣE= ar will be
M oracle calls (the remaining proof is exactly the
N
01,(
jES,
Our estimator is unbiased because
N Σ
Σ
M
a1,66)
aij.
N
jES.
j=1
We can use Hoeffding's 's Inequality to show that
N
M Σ Oi,
eM
Pr
Σ
M
Di,j
ai
Pr
Σ
((,(())
N
4N
ai.j
jES.
j=1
jES.
j=1
222
(Σ)= az,))
< exp
16NT
M - )
23 MN/CY
S 2exp
C6
2 16C1
2exp
SC* log(40.))
which is true by our assumption on M. A union bound over all [N] allows us to show that get (1 e/44 approximation of Σ aij for all i with probability least 0.95.
which is at most 20N M >
22
E bit for all 1 < N. Let i E S, for some 1 < t M We pick Σ E ans random permutation of [N]. and define
Step 2: Approximating
28

---

and furthermore
wo"=
WQQ Oaxd
Wkk
Odxd WK
(ddxd) W
The output softmax (K"" gives us exactly
Ejes, 61,76)
EjEs, at,+(1)
which will be our estimator. First observe that
N
M
E
bL.
Σ
big
N
JES.
j=1
We can again use Hoeffding's 's Inquality to show that
E² || brr 113
N
Pr
bw.r))
Σ
bis
big
2. exp
M
(2xx2 [|
JES.
M2
2 exp
128
which is at most
20N when M
128(log d+ log 10+1og N)
We have shown that
82
N
Σ}= Ui.jj
N
S EjEs, ai,r(1)
$ (1 - =/4))M
(1 + ++/44)M
and now we prove
N
Ej aij
N
Σ
b
b(r())
S
Σ
b 122
Ejes, ai,66) 2
j=1
jES,
5=1
which concludes the proof. Indeed, we first decompose
Σ
bid
Σ
bi.r()
Σj=r Oij
11
bi.
bi)
N
+ (1 -1))
8) Σ
bir(i)
N
Ejes, (i,7(1)
M
M 2
==1
JES.
j=1
JES,
JES.
N
N
N
bi
bi
+ +11- [1)
bi,7
M
M 2
JES,
JES.
where
1
M Ex= Aijj
1
<8
<
1 + E/4
N. Ejes, ai,((j)
1 1- 8/4
Now already know
Σ
bis
N
8 S
Σ
M
2
4
JES.
j=1
and therefore Equation can be further bounded by
N
bi.
+ (1 - (0) + +/44]
Σ
bis
11
4
j=1
N
N
8
bu
+ 4+
(1 + e/4)
Σ
ba.t
4
j=1
N Σ
b
2
j=1
which concludes the proof.
29

---

C.2 Missing Proofs in Section 4.2
Theorem C.2 (Theorem 4.2 4.2). Given M instances of single layer, single head transformers with input length M and embedding dimension d. there exists an algorithm that simulates them with one call of single layer, single head transformer with input length ( and embedding dimension O(d), along with O M many matrix multiplications of size M
Proof. We assume that the input/layer MLPs in all the instances are identity functions for the same reason in Lemma B.1 Let X, IR Mxd be the input, W W.K W.V' Rdxdd be the query, key and value matrices for each instance < N. Our goal is to calculate
voftmax((X,))) ) (XWW))
for all 1 i M- We first compute X.W, X,W, , for all 1 sis N M will denote
For convenience
B. = (x,W 1. = (X,W, 1o. b. = (X, [
such that our goal is to compute (9., ( (X,W)) for all S S N .115j M. For convenience we let
| (|W, l2, |X ||W 12. |X IIW 1l2 S C poly(NN,
for some C' (because we assume that all entries have Ollog N) bit representation, and therefore each parameter is at most poly(N)) As result,
-C² (gigshi ke C², ||w/ll2 S
for any 1 i N/M, 1 أزمك' S M.
Let B E R be determined. Define
U1.
37
such that (112) N/M (we only need S O(log(N/M)) by Stirling approximation) and all u, have exactly r/2 zeros (if there are more vectors than needed, simply make sure they are distinct), and let
0 = B (1) us
17 such that (u, v²) 0 for all i. For any i + j. notice that there must exist an index at which u; is -B and vy is B. This is because the set of nonzeros v; is the compliment of the set of nonzeros in us, and the former set must be different from the set of nonzeros in Uy. Now append u, to 4, to get q'. and i; to ki,j to get K for all S < M. Set = d + r. For each pair of dh and k/.""
for all 1 sis S N
if Y, i.e. as and by are in the same small transformer instance, then (di Kly ) (gi.) ) (wi, vp) = (gi.s kr)r)
if # i.c qs and ky are in different small transformer instances, then (gi.g ky ) + (M, ug) (9 kv B²
(gh. ke
Now we let Q E Nxd be the matrix of yhyy and K E IR Nxd' be the matrix of Ki, and V = -YWY. set [Q,K,V] R. (3d')) (note that we can always pad zeros to V to make dimensions match),
(x' Oaixa Oxx
Ow x Tax Ox
Ow xd! Oar x La x
we=
wv
such that
12,K, VIW2
Q,Q,
= =V.
30

---

Furthermore, for each query (g.,- uz), its inner product between all keys in the same small transformer will be preserved, while its inner product between all keys in a different small transformer will be at most C B². Therefore, for each query li.j. we can calculate the error as:
M expl(ys.jk
N/M
M
exp((g Ke, Ex=1 exp((1ass k(e))
Σ
Ee expl (xpl(yt.jiki kite))
11
N/M 11
#=1
f==1
exp( Rig
expl ( k(gg)))
exp((gr.) k()e)) Ei=1 M
N/M 1=
Σe= expl
#=1
NC exp((22 -2) B²)
Ee E== expl(gt.) ki,e))
M
expl (9pp(19.511 (gt
expl ki.y))
Ua.t 11g
t=1 exp( (gi,) ks,e))
E Σx= exp ( Ke
j'=l
NC exp(2pCC2 B²)
+
M Mexp( C2)
Now notice that
N/M
N/M
M
Σ
Σ
exp((1 k(,e)) Σ expl(gns, +
Σ
Σ
exp xxp(ldisskeee) k(,))
and that
M
M Mexp(-C²) < Σ
(up ka,)) S M exp(C²)
1=1
N/M
M
Nexp(-C2- B2) <
Σ
(xp, s N -
As result,
cx -B2)
N Nexp(2C2 B²)
Ees exp(lgi,, Therefore, we can further upper bound the error by
Σm
N/M EM expl k())))))
M exp(-((2)
M
ccxp(2C2 B²)
NC cxp((2 -B2)
M exp((C²)) .C C
+
M
M exx(-C22
eCCepp2222 - B²) + exp(C²))
M
Therefore, set B Poly(N) to be sufficiently large such that the error is (
D Missing Proofs in Section 5
Theorem D.1 (Theorem 5.1]. For any transformer TT with L layers, attention heads in each layer, input length N, embedding dimension d, constant-size sliding window, there exists algorithm that simulates T with O N HE calls to a transformer oracle with E' layers, H' attention heads in each layer, input length M and embedding dimension O dH' with causal masking. This result still holds if we have constant-sizz attention sink.
M H'
Proof. The proof goes in the same way Theorem B.S where assume without loss of generality that H L = H' L' We start with the sliding window scenario where the size of sliding window is Notice that for each query qi (i r 1) we want to compute
exp( k2)) = Σ exp kg))
exp((gn,k)))
31

---

and
exp((gn; ky)) Uj
exp explign ky)) V/ exp kg)) .ij
given window size r. In addition, we can compute Σ j= exp (gs, kj)) and Ej=1 exp k()) 2g for all & r with 2 oracle calls, as shown in the proof of Theorem B.3
We will partition {r+l,.... .N into chunks Sj +........ M) of size r and approximate the terms above for all E S each chunk using constant many oracle calls, which suffices since is a constant. Without loss of generality we only prove our claim for Si as the proof can be easily generalized to the remaining St. Indeed, observe that
{M+1, 2M -
expl ky)) and exp((1 ky))
for all S can both be computed exactly with one oracle call using the proof of Claim B.6 Furthermore, one oracle call suffices to compute either
ex-rexp((ur ki)) vi
Σj exp((es: kz)) U/
Ej= exp( kj))
Σj= exp( (gi, kz))
for all Si because we can feed the oracle with [[S), :] and use W project X[S to (ge-1,..- 1.... gar) and use W to project [ to ..i,..., kM-r) (similar to proof of Lemma B.I..
Finally, when there are attention sinks, we simply need to further calculate Ej=1 exp((a, ky)) and Σj=1 exp( ky)) vy. Observe that
Σ exp((1s, k,)) =
Σ
expl (g; kg)) - Σ
(9)(()
==1
j=s+1
exp((an k2)) U/
Σ
expl
k2))
exp( Uy.
j=1
f=
Each of the four terms can be computed with the exact same technique as in sliding window with oracle call.
32


Reviews:
[{"review_id": "CiUvSRBok3", "reviewer": "Reviewer_6Vvf", "summary": "In this work, the authors propose to use small transformers to approximate the output of a large one. This study highlights:\n\n1. This paper explores the representational power of small Transformers in simulating large Transformers that process long input sequences. \n\n2. Such simulation can potentially save inference and training cost as modern GPUs are optimized for shorter sequence lengths.\n\n3. A Transformer with input length $ N $ can be efficiently simulated using $ O\\left((N/M)^2\\right) $ smaller Transformers with input length $ M \\ll N $, and this quadratic bound is tight in the worst case.\n\n4. This conclusion could also be extended to transformers with sliding window attention, or attention sinks.", "questions": "1. In the study, the transformer model is simplified to merely containing MLP and Attn blocks. In a real transformer model, things are much more complex, such as rotary embedding, skip connection, layer normalization, etc. Should these partitions draw to a different conclusion?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. This paper is well written and easy to understand. The notations and equations are self-consistent and conclusions are presented in clear format.\n2. It is innovative to simulate a large transformer with smaller ones. The authors made remarkable progress compared to related works.", "was_revised": true, "final_justification": "I suggest Accept. My primary considerations about this paper are:\n\n1. This paper is well written. It focuses on a very important topic (smal vs. large model) which still lacks theoretical analysis. I believe that the meaning behind this paper is the most important.\n2. Questions on why the authors apply such simplicity and why the simplicity is reasonable are clearly addressed by the authors. This is important because this indicates that the assumption closely related to reality.\n3. Although empirical validation is not included (as pointed out by some reviewers), I believe this may go beyond the domain of this paper. Lacking validation would not diminish the contribution of this work. I think this is not a main drawback.", "rebuttal": "We thank the reviewer for the thoughtful comments, and answer the questions below.\n\n\n**Transformer model simplification:** This is a great question! We simplify our transformer model for the sake of simpler theoretical analysis, but in general these additional components will not affect our conclusion, and the reason is that whatever component we add to the large transformer, we can also add it to the small transformers in the same way to ensure that our analysis still holds.\n1. Rotary embedding: When a large transformer has rotary embedding, each query and key is “rotated” by some fixed rotation function in each attention head. The same rotation function can be applied to each query and key in attention heads in small transformers as well.\n2. Skip connection: One can usually think of skip connection as if we have an additional attention head (let’s call it skip attention head) in each layer whose output is identical to input. This additional attention head can be easily simulated by $N/M$ smaller skip attention head because we can feed the input of length $N$ to $N/M$ many smaller skip attention heads. Therefore, if both large and small transformers have skip connections, a large one will still be simulated by small ones (number needed is still the same).\n3. Layer normalization: Layer normalization will not affect our analysis because whatever normalization that is performed in large transformers, we can do the exact same in small transformers. Therefore, if both large and small transformers have layer normalization, a large one will still be simulated by small ones (number needed is still the same).\nWe will make sure we mention this in the final version of the paper.\n\n**Abstract is limited to one paragraph:** Thank you for pointing this out, and we will make sure we fix it in our final version.\n\nWe hope that our answers make sense, and make the reviewer more confident about the value of our work. Please let us know if there are any more questions!"}, {"review_id": "Nif16tpzRS", "reviewer": "Reviewer_tBwa", "summary": "Evaluating large language models (LLMs) on lengthy sequences is computationally intensive due to the quadratic cost of their attention mechanisms. This work presents a method to address this challenge. The authors developed a theoretical framework that effectively simulates a large transformer with a sequence length of N by using O((N/M)^2) transformers, each processing a sequence of length M (where M is much smaller than N). Furthermore, they extended this framework to accommodate different attention mechanisms, such as sliding windows and attention sinks, which significantly reduces the requirement to just O(N/M) smaller transformers. They also found that, on average, a linear number of transformers are sufficient for the general case, provided that attention and value parameters are bounded.", "questions": "* The authors covered sliding windows and attention sinks, but they didn't mention the causal masking case. I assume it might follow the same quadratic scaling as the general case, but I'm curious if its specific structure could allow for a more efficient simulation.\n* I'm curious about KV-caching; can it enhance the suggested algorithm?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths - \n* This paper tackles a critical problem in the field of large language models. Creating efficient algorithms—perhaps using distributed computing—for LLM inference on long sequences could significantly boost performance.\n* This paper is highly readable and well-structured. The theorems are presented clearly, and the proof sketches offer concise explanations of the authors' methodology.\n\nWeaknesses - \n* The paper would benefit significantly from empirical validation or a proof of concept. The oracle constructions proposed in Section 3 appear plausible, and some practical results would be highly valuable. For instance, an inference efficiency comparison across different values of M could effectively illustrate the trade-off between practical benefits and theoretical compexity. Additionally, it would be insightful to understand where real-world data falls on the spectrum between quadratic and linear scaling. Given the clear potential impact on practical applications, including some empirical results is crucial.", "was_revised": true, "final_justification": "Despite the extensive theoretical framework presented in the paper, I believe that additional empirical validation is necessary for the work to feel complete. As such, I will not be increasing my score.", "rebuttal": "We thank the reviewer for the insightful comments, and answer the questions below.\n\n**Empirical validation and parameter tuning:** We agree that our paper gives rise to many interesting questions which should be the study of follow-up empirical work. However, there are two main reasons we chose not to include them here. \n\nFirst, we feel that the theory results presented in our paper stand on their own. The goal of our work here is to perform a complete theoretical analysis of how small transformers can be used to simulate big ones. It is important to nail down these precise dependencies before implementing the approach in practice, and that is exactly what we do here - we provide a complete and systematic analysis, including optimal and yet simple simulation algorithms. Most notably, some of our results show that surprisingly efficient simulations are possible (for example, Theorem 1.1 and Lemma 3.3 show that we can make use of all the layers of an oracle simultaneously), and we’re also able to rigorously pin down when techniques like attention sinks, sliding window, or assumptions on the data can yield real improvements. \n\nWe also want to highlight that our results indicate that quadratic/linear amounts of small transformers have at least as much representational strength as a constant amount of large transformers in different settings. Such general representation results can only be proved mathematically/theoretically.\n\nSecond, an empirical validation of our results here that is truly meaningful would need to relate to real LLMs that are trained on large corpa of text. The implementation and parameter tuning can now build on our results, but this would be a substantial undertaking, and likely depends quite a bit on the setting (data, hardware etc). Our simulation algorithms are simple and even “differentiable”, and therefore could be implemented effectively in practice. \n\nFor these reasons, we feel that careful experimental work should comprise a second paper (or perhaps even more than one follow-up paper for different applications).\n\n**Causal masking:** We state in our main Theorem (Theorem 1.1, line 107-108) that indeed, a quadratic amount of small transformers are able to simulate a large one, assuming they both have causal masking. A similar argument to the one in line 109-113 will show that this is optimal as well.\n\n**KV cache:** This is a great question! Our algorithms are indeed compatible with KV cache because it can be used in a standard way for small transformer inference. The trivial space needed will be $O(N^2/M^2)\\cdot O(Md) = O(N^2d/M)$ for the main simulation. However, in our actual construction, we only need to store what needs to be stored in a large transformer inference (all keys and values) plus a constant amount of fixed vectors such as the all one vector. As a result, the space needed is $O(Nd)$, which is exactly the same as normal KV cache takes.\n\nWe hope our responses make sense, and please let us know if there are any more questions!"}, {"review_id": "MSA38x9Uzi", "reviewer": "Reviewer_BQJT", "summary": "This paper proves the existence of an algorithm to tightly approximate the output of a transformer with a context length of $N$ by making roughly $O((N/M)^2)$ calls to transformers with a shorter context length $M$, where $M \\ll N$. While this algorithm still requires a quadratic number of operations relative to the context length, the authors suggest this decomposition could be leveraged to achieve wall-clock time speedups if modern GPUs/ASICs provide fast inference for moderate-to-short contexts. They also show that $O(N/M)$ calls to smaller transformers is optimal in streaming settings and in cases where key, query, and value elements are in relative close proximity.", "questions": "**Questions:**\n\n1. It would be very helpful if you could provide more insight into when your method might yield the most gains. For example, for what context lengths ($N$) and model sizes does it provide the most benefits? Is it more helpful for prompt processing (pre-filling) or the inference stage?\"\n\n2. Is it fair to say the core of the proposed decomposition is Lemma 3.1, which decomposes a single large attention computation into multiple smaller ones? If so, how does this theoretical decomposition compare to implementations like FlashAttention, which also use similar tiling and softmax calculation tricks?\n\n3. The actual algorithm is not provided in the paper, but proofs of existence/correctness are presented. Is it possible to present the algorithm itself, or at least provide more insight on it?\n\n4.  Is the approximation error caused by the \"$O(\\log N)$-bit representations\" assumption, or is the approximation a general part of the algorithm, even at full precision?", "limitations": "In my opinion, the lack of experimental results is not properly acknowledged in the limitations section: \"our algorithms are efficient in theory, and we expect them to be efficient in practice as well\"", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n\nThe paper is very well-written and well-organized. I particularly appreciated that the authors provided informal versions of their main results in Section 1.2 and gave additional insights before diving into the full technical details. Also, the roadmap for the proof and the proof sketch of Lemma 3.1 are helpful for understanding the gist of the theory. Finally, the main result of the paper is very interesting on its own.\n\n\n**Weaknesses:**\n\nThe main weakness of the paper is its lack of empirical evidence to support the claimed performance gains. I understand this is presented as a theory paper; however, its premise and goal is purely practical: to introduce a new method for handling long input sequences by leveraging modern GPUs. Therefore, the absence of experimental results makes its applicability questionable.\n\n1. The method's applicability hinges on the paper's argument that \"modern GPUs enable faster transformer inference with respect to the wall-clock time when the input sequence is short-to-moderate, then our algorithms allow faster wall-clock time inference.\" This critical, hardware-dependent condition is influenced by many factors, and whether it actually holds true needs to be shown experimentally.\n\n2.  The number of calls to the oracle models can be very large. For instance, if $M \\approx \\sqrt{N}$, the method makes $O(N)$ calls to potentially $O(N)$ different models. Although the authors claim the \"total number of parameters does not depend on $N$,\" it is unclear how the overhead of calling many (even slightly) different models compares to using one model over the whole context.\n\nDetermining if the proposed method provides any reasonable practical gain, and in what regime, depends highly on intricate hardware details (e.g., whether the pipeline is memory- or compute-bound), which can only be clarified through experimental results.\n\n3.  The paper proves the existence of an algorithm that \"approximates\" the output of the large transformer. While the authors quantify the approximation error, it remains unclear how this error affects model performance compared to other long-context attention alternatives, which again can only be judged in practice.", "was_revised": true, "final_justification": "After carefully considering the authors' responses and the discussion among the other reviewers, I still believe the main weakness of the paper is its lack of empirical evidence to support the claimed performance gains. While I understand that this is presented as a theoretical paper, its premise and goal are fundamentally practical: to introduce a new method for handling long input sequences by leveraging modern GPUs. Therefore, the absence of any experimental results raises questions about its real-world applicability.", "rebuttal": "We thank the reviewer for the detailed comments. We address the questions and concerns below.\n\n**Empirical validation (and acknowledgement):** We agree that our paper gives rise to many interesting questions which should be the study of follow-up empirical work. However, there are two main reasons we chose not to include them here. \n\nFirst, we feel that the theory results presented in our paper stand on their own. The goal of our work here is to perform a complete theoretical analysis of how small transformers can be used to simulate big ones. It is important to nail down these precise dependencies before implementing the approach in practice, and that is exactly what we do here - we provide a complete and systematic analysis, including optimal and yet simple simulation algorithms. Most notably, some of our results show that surprisingly efficient simulations are possible (for example, Theorem 1.1 and Lemma 3.3 show that we can make use of all the layers of an oracle simultaneously), and we’re also able to rigorously pin down when techniques like attention sinks, sliding window, or assumptions on the data can yield real improvements. \n\nWe also want to highlight that our results indicate that quadratic/linear amounts of small transformers have at least as much representational strength as a constant amount of large transformers in different settings. Such general representation results can only be proved theoretically.\n\nSecond, an empirical validation of our results here that is truly meaningful would need to relate to real LLMs that are trained on large corpa of text. The implementation and parameter tuning can now build on our results, but this would be a substantial undertaking, and likely depends quite a bit on the setting (data, hardware etc like the reviewer suggests). Our simulation algorithms are simple and even “differentiable”, and therefore could be implemented effectively in practice. \n\nFor these reasons, we feel that careful experimental work should comprise a second paper (or perhaps even more than one follow-up paper for different applications). We will modify the limitation section - thank you for pointing it out.\n\n**Whether modern GPUs can do faster transformer inference needs to be shown experimentally:** Our main argument here is that when processing an extremely long input sequence, it is possible to partition the input sequence into multiple segments and deal with them separately while still obtaining the correct inference output. For example, we prove that a single GPU that can only take input length of at most $M$ can still perform inference on sequences of $N\\gg M$ by doing inference multiple times. It is not clear what a straightforward/trivial time (wall-clock, FLOPs, etc) to compare to even is, because it is initially unclear how inference can even be performed with such limited resources.\n\nIn addition, the fact that transformer-specific GPUs allow faster inference on short-to-moderate input length has been experimentally verified and is a core idea for many startups, as we mentioned inline 31-32. For example, Etched’s Sohu ASIC claims to be 20x times faster than NVIDIA H100 on Llama 70B (we are not allowed to add links here due to Neurips rules, but the details can be found on Etched’s website). \n\n**Number of calls to different models could still be very large:** We are not sure if we fully understand what “different models” here mean. We only consider transformers, so as long as all the models are based on the transformer architecture, our analysis will hold. Our assumption here is that the small transformers have all the intricacies of the large ones: if the large transformer has rotary embedding, skip connection, layer normalization for example, the small ones can simulate it if they also have the same components.\n\n**Output approximation and bit precision:** Our main result (Theorem 1.1) provides an exact algorithm if we assume infinite (full) bit precision. The reason we define simulating as an approximation up to $O(1/2^{N})$ multiplicative error is that, as in most theoretical works in this area, we assume only $O(\\log n)$ bit precision to more accurately model realistic hardware, which means that all parameters are represented by $O(\\log N)$ bits. In this case, it is impossible to achieve perfect accuracy because the $exp$ function in the attention mechanism will have to be approximated. In other words: this approximation error is unavoidable in limited-precision hardware. Our results provide the best possible approximation in this scenario. \n\n**More insights on model size vs gains:** Our main results require around $2N^2/M^2$ small transformers (or calls) to simulate a large one, so in theory the larger $M$ is, the fewer inferences we need to perform. We agree that tuning $M$ (and other model parameters) and finding out the regime where we can obtain most gains is an interesting empirical problem to study in the future.\n\n**Is the core of the results Lemma 3.1 and comparison to Flash Attention:** This is a great question! Yes, Lemma 3.1 is one core of our proof (the other core being Lemma 3.3 where we deal with multiple heads and layers) and it shares some insights with Flash Attention, although they are still different.\n\n1. Similarities: Both Flash Attention and our algorithm deal with a large attention matrix by decomposing it into smaller blocks. \n\n2. Differences:  The goals are different: the major concern of Flash Attention is IO complexity, and here we study representational strength. In addition, the main technical challenge is different: in Flash Attention, you load query, key, matrix value blocks into SRAM and do whatever computation you can do on SRAM, while here we can only perform what small transformers can perform. Therefore, our model is more limited.\n\n**More insights on our algorithms:** We present proof sketches in section 3 for our main results. Although the algorithms for average-case inputs and attention sinks are slightly different, they share similar ideas. Proof sketch of Lemma 3.1 (starting from line 273) best summarizes our ideas. We will make the sketch clearer in the final version of this paper.\n\nWe hope that our responses make sense, and make the reviewer believe that our work has its important value even though it is purely theoretical. Please let us know if there are any more questions!"}, {"review_id": "gxIXUbdQet", "reviewer": "Reviewer_TTT1", "summary": "This paper theoretically prove that large transformer (input length N) can be simulated by no more than $O((N/M)^2)$ small transformers (input length M, where M << N) with acceptable errors. Some practical scenarios like masking, sliding window and attention sink are also considered in this paper. This theoretical result may be useful for efficiently processing long sequences by leveraging hardware optimizations designed for smaller sequences.", "questions": "Q1: This paper provide a $(1+\\epsilon)^2$ multiplicative error bound for a single layer. Will the errors explode when considering practical Transformer with multi-layer and other non-linear components like LayerNorm and  feed forward layer?\n\nQ2: The Abstract claims that a large Transformer can be efficiently simulated by only $O((N/M)^2)$ small Transformers, and that this cannot be improved in the worst case.\n\nHow to understand \"cannot be improved\"?        Have the authors proved it?\n\nQ3: Since this paper mentions that modern GPUs can accelerate small input sequences in transformers, it is recommended that the authors consider performing some experients to support the utility their algorithm.", "limitations": "yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 1, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. This paper proves that large transformer can be simulated by multiple small transformer, and establishs the guarrantee for the worst-case inputs: quadratic small transformers are sufficient and necessary.\n\n2. The paper's simulating method preserves the representational strength of standard Transformers. The simulation error for a single layer is bounded by a $(1+\\epsilon)^2$ multiplicative error bound.\n\n3. The paper considers practical setting like causal masking, sliding window, and attention sinks.\n\nWeaknesses:\n\n1. Lack of experiments: While I believe that multiple small models can simulate a large model from the perspective of representational strength, the viability of the algorithm should be verified by experiments. \n\n2. The writing is redundant: Definition 2.3 - 2.5 are very similar (page 6). Theorem 3.4 and Theorem 3.5 differ by only one word (line 337-346).\n\n3. The theorems are informal: The theorems in this paper are mainly text-based and are not expressed mathematically, which affects readability.\n\nMinors and Typos:\n\n1. The title formatting does not follow standard academic capitalization conventions.\n\n2. The abstract should be limited to one paragraph.\n\n3. criticaly -> critically (line 79)\n\n4. Vectors and matrices should be bolded", "was_revised": true, "final_justification": "I agree that your theoretical results are interesting, but I do not think the readers would be willing or easily follow your work without empirical foundation.", "rebuttal": "We thank the reviewer for the comments. Here are our responses.\n\n**Empirical validation:** We agree that our paper gives rise to many interesting questions which should be the study of follow-up empirical work. However, there are two main reasons we chose not to include them here. \n\nFirst, we feel that the theory results presented in our paper stand on their own. The goal of our work here is to perform a complete theoretical analysis of how small transformers can be used to simulate big ones. It is important to nail down these precise dependencies before implementing the approach in practice, and that is exactly what we do here - we provide a complete and systematic analysis, including optimal and yet simple simulation algorithms. Most notably, some of our results show that surprisingly efficient simulations are possible (for example, Theorem 1.1 and Lemma 3.3 show that we can make use of all the layers of an oracle simultaneously), and we’re also able to rigorously pin down when techniques like attention sinks, sliding window, or assumptions on the data can yield real improvements. \n\nWe also want to highlight that our results indicate that quadratic/linear amounts of small transformers have at least as much representational strength as a constant amount of large transformers in different settings. Such general representation results can only be proved theoretically.\n\nSecond, an empirical validation of our results here that is truly meaningful would need to relate to real LLMs that are trained on large corpa of text. The implementation and parameter tuning can now build on our results, but this would be a substantial undertaking, and likely depends quite a bit on the setting like the reviewer suggests. Our simulation algorithms are simple and even “differentiable”, and therefore could be implemented effectively in practice. \n\nFor these reasons, we feel that careful experimental work should comprise a second paper (or perhaps even more than one follow-up paper for different applications).\n\n**Writing is redundant; theorems are informal:** Although Definitions 2.3-2.5 are similar, we believe that it is important to distinguish causal masking, sliding window and attention sinks as they are all different in practice. In addition, these differences will affect our proof details, so we want to make sure that they are stated as clearly as possible; we need to formally define all the different terms and models, even if some are similar to each other, so that we can formally state and prove all our results. As for Theorem 3.4 and 3.5, we want to emphasize Theorem 3.4 as our main result whose proof is based on the lemmas in section 3, while Theorem 3.5 uses a different set of lemmas that are presented in appendix (supplementary material). The statements may appear similar, but they require substantially different work to prove.\n\nOur main result (Theorem 1.1) is stated formally in mathematical language. We use informal theorem (Theorem 1.2) for average case results because of the page limit, and we believe that this makes our results easier to understand in the introduction. All the precise, formally-stated theorems are presented and proved in the supplementary material.\n\n**Typos and formatting:** Thank you for the suggestions. We will adjust them accordingly.\n\n**Multiplicative error bound for single layer:** Our main result (Theorem 1.1) provides an exact algorithm if we assume infinite (full) bit precision. The reason we define simulating as an approximation up to $O(1/2^{N})$ multiplicative error is that, as in most theoretical works in this area, we assume only $O(\\log n)$ bit precision to more accurately model realistic hardware, which means that all parameters are represented by $O(\\log N)$ bits. In this case, it is impossible to achieve perfect accuracy because the $exp$ function in the attention mechanism will have to be approximated. In other words: this approximation error is unavoidable in limited-precision hardware. Our results provide the best possible approximation in this scenario. \n\n**Cannot be improved in the worst case:** Our main theorem (Theorem 1.1) states that $O((N/M)^2)$ small transformers suffice, and we discuss in line 109-113 that this is also optimal under standard complexity-theoretic assumptions. So yes we have proved it, but we did not make it a formal theorem because the argument only requires a few sentences.\n\nWe hope our responses make sense, and we sincerely hope that the reviewer can reevaluate our work as we believe that our work has its important theoretical values. Please let us know if there are any further questions!"}]

Author rebuttal:

Meta-review: This work considered the question of whether transformers with long sequences can be efficiently simulated by transformers that can only take short input sequences. It proved that any transformer with input length N can be efficiently simulated by O((N/M)^2) transformers with input length M, and proved that this is the best bound in the worst case. It then considered several beyond-worst-case scenarios and showed the optimal bound O(N/M).

The work proposed a novel and interesting question (simulating transformers on long inputs via transformers on short inputs), which can also be relevant to practice since it points to a potential new direction for acceleration (though not concrete practical algorithmic ideas). 
The theoretical analysis is thorough, giving optimal bounds in the worst case, and also optimal bounds in several beyond-worst-case scenarios that may be relevant to practice. 

Overall, the work is a solid theoretical work: asking an interesting question along an important direction and giving a thorough analysis with optimal bounds. The fact that the theoretical question/results are relevant to practice should be regarded as an additional benefit rather than a drawback.
Decision: Accept (spotlight)