Encoder-only Next Token Prediction
Authors: Ethan Ewer
Daewon Chae
Thomas Zeng
Jinkyu Kim
Kangwook Lee
Venue: Accepted by TMLR ()

Abstract: Next-token prediction is conventionally done using decoder-only Transformers with causal attention, as this approach allows for efficient reuse of keys and values. What if we were not compute-limited, should we still use decoder-only Transformers? In this work, we introduce Encoder-only Next Token Prediction (ENTP). We explore the differences between ENTP and decoder-only Transformers in expressive power and complexity, highlighting potential advantages of ENTP in settings with unbounded compute. We introduce the $\operatorname{Count3}$ task and show, both theoretically and experimentally, that while ENTP can perform this task easily, a decoder-only Transformer cannot. Finally, we empirically demonstrate the superior performance of ENTP across representative tasks where next-token prediction based Transformers can be evaluated, including addition, in-context learning, and language modeling.

Published in Transactions on Machine Learning Research (11/2025)
ENTP: Encoder-only Next Token Prediction
Ethan Ewer* University of Wisconsin-
eewer edu
Daewon Chae Korea University
cdud998korcc..cc.
Thomas Zeng" University of AisconeinnMMdison
tpzeng@wiisc.cm edu
Jinkyu Kim Korea University
Sinkyalkimkkoree.cuu oc.kr
Kangwook Lec
kangwook. lee Swwisc.
University of Wisconsin- Madison
Reviewed on OpenReview: https: // opw.r/vien.e.e.... net/ forum? CGWo289ySe
Abstract
Next-token prediction conventionally done using decoder-only Transformers with causal attention, this approach allows for efficient reuse of keys and values. What if we were not compute-limited, should we still use decoder-only Transformers? Tn this work, we introduce Encoder-only Next Token Prediction (ENTP). We explore the differences between ENTP and decoder-only Transformers in expressive power and complexity, highlighting potential advantages ENTP in settings with unbounded compute. We introduce the Count3 task and show, both thcorctically and experimentally, that while ENTP can perform this task easily, decoder-only Transformer cannot. Finally, we empirically demonstrate the superior performance of ENTP across representative tasks where next-token prediction based Trans- formers can be evaluated, including addition, in-context learning, and language modeling.
Introduction
Traditionally, auto-regressive language modeling has relied on decoder-only Transformers VVawwani et al, 2017) with causal attention, trained using the next-token prediction objective. Causal attention ensures that each token can only attend to previous tokens, preventing future tokens from influencing past outputs. This mechanism makes training and inference more efficient, as past keys and values do not need to be recomputed for each token. This efficiency enables the scaling of decoder-only Transformers, such as GPT-4 (Achiam) et al. 2023 and Llama-3 (Dubey al. 2024). up to billions of parameters using current hardware.
However, causal allention also introduces artificial constraints. Given tokens Iı, -.., the contextual embedding of zj (where j < n) can only attend to embeddings of earlier tokens, even when predicting In+1- While this constraint ensures a strict causal structure, it may not always be necessary or benoficial. We investigate what happens when we remove this constraint, while still maintaining causality externally.
Specifically, we look at Encodcr-only Transformers, which are typically used for tasks like classification, and do not impose this causality constraint. Though traditionally not used for auto-regressive tasks, encoder-only architectures be adapted for next-token prediction. When computing the output at the current time step, an encoder-only Transformer, or any sequence model, can be made causal by only providing inputs up
"Equal contribution.

---

Published in Transactions on Machine Learning Research (11/2025)
x2
x3
x4
x2
x3
x4
Encader
Eacodox
Encodor
301
xc2
x3
Decoder-Only Next Token Prediction
Encoder-Only Next Token Prediction (ENTP)
Figure Decoder-only vs. Encoder-only Transformers in next token prediction. Decoders use causal attention, ensuring that each token attends only to the preceding tokens. In contrast, encoders allow all lokens to attend to each other by performing attention computation from scratch for each token prediction.
to and including the current time stop (see Figure 1 Therefore, in this work, we investigate the idea of using encoder-only Transformers for next-loken prediction. We summarize our findings below.
Functions expressible with Decoder-only and Encoder-only Transformers. We demonstrate that the sets of functions expressible by decoder-only and encoder-only Transformers are not comparable, which goes against intuition that the expressivity of encoders would subsume that of decoders. Rather, there exist functions expressible with decoder-only Transformers that not expressible with encoder-only Transform- ers, and vice versa, as well functions expressible by both architectures.
Complexity of Decoder-only and Encoder-only Transformers. Based on the minimum time and space complexities, we give description of the functions that can be performed by decoder-only and encoder- only Transformers. We proposc an auto-regressive task that can be performed by encoder-only Transformers, and cannot be performed by decoder-only Transformers (given that some mild assumptions hold). We validate our hypothesis with small experiments using small decoder-only and encoder-only Transformers, as well as experiments fine-tuning GPT-40 (Achiam et al., 2023 Llama3-813 (Dubey et al. 2024), and BERT (Devlin al. 2019).
Experiments on Small-Scale Language Modeling Tasks. We compare the performance of decoder- only and encoder-only Transformers on a range of small-scale language modeling tasks. We test the sample complexity and length generalization capabilities of decoders and encoders using arithmetic tasks (Lee et al. We also train both models to perform in-context learning (Garg et al. 2022 on various simple fune- Additionally, we train small decoder-only and encoder-only Transformers text dataset (Gokaslan
2023
lions.
et al.
2019 and assess their performance on language modeling tasks.
2
Related Work
Expressive Power of Transformers. There have been various literature exploring the expressive power of Transformers. From the lens of universal approximation, Yun et al. (0020) showed that any continnous seguence-to-sqquene function over compact set be approximated arbitrary close by Transformer (of finite albeit very large size). Other works approach expressiveness from the perspective of computability and complexity such as [Pérez el al. (2021) which showed Transformers are Turing complete and Merrill el al. b2022; Merrill & Sabharwal (2024] Li et al. (2024) which use circuit complexity to characterize the languages recognizable by Transformers of fixed depth. Giannou et al. (2023) presents a framework for Transformers as universal computers by placing them a loop. Communication complexity has also been used show the impossibility of one-layer Transformers of expressing certain functions e.g. induction head, without the
2

---

Published in Transactions on Machine Learning Research (11/2025)
model size being linear in the length of the imput (Sanford et al. 2024b a). We note that the existing bounds (Sanford et al. 2024bb ap are highly related, but they do not directly imply the relative expressive power of encoder and decoder (and specifically of the same fixed model size).
Transformer Architectures for Next Token Prediction. Transformers have become the de facto back- bones for next-token prediction tasks, leading several variants such as encoder-decoder, causal decoder- only, and prefix docoder-only models. In the encoder-dccoder model (Lewis al. 2019 Chung et al., 2024), similar to the vanilla Transformer (Vaswani al., 2017), the encoder transforms the input tokens into con- ditioning features, and the decoder suttoreeressivvlly predicts the target tokens by using cross-attention over the encoded representation and cansal attention over the output tokens. In contrast, the causal decoder-only model (Brown et al., 2020; Chowdhery et al. 2023 uses only the Transformer decoder and applies causal attention to all tokens to perform next-token prediction, ensuring that each token attends only to previous tokens. The prefix decoder-only model (Raffel et al., 2020 Wu et al.) 2021) is similar to the causal decoder- only model but differs in that it applics non-causal attention (i.e., full self-attention) to the input sequence (see Figure g for visualizations of the attention patterns in these variants).
With the development of these models, recent studies have investigated the performance of each variant across various tasks. Notably, Wang et al. (0222) examined the zero-shot generalization performance of each model along with various objectives, and Ding et al. (2224) analyzed the performance of causal decoder-only and prefix dccoder-only models in in-context learning. Patel et al. 2023) showed that bidiroctional language models, trained with denoising objectives such as masked language modeling, can be prompted in an auto- regressive manner, achieving performance comparable larger decoder-only Transformers. Building on this foundation, ENTP explores the training of bidircctional language modcls using auto-regrossive objectives.
3 Preliminaries
Sequence-to-Token Functions and Autoregression. Given a vocabulary V (which we traditionally think of as some finite set, but could in general be any arbitrary perhaps unconntable set e.g. Rd), we can define a sequence over V as (I1,..., Fnn) where F1,..., E V. Let V = {(=1,.... .n)) E N; E V) be the set of all sequences generated by V. Then, we say that f:V* V + V is a eequence-to-tokes function.
We can view a causal model as a map from an input sequence to an output sequence with the causality constraint that the i'th output token depends only on the first input tokens. Mathematically, we enforce this causality constraint by characterizing our causal model, Ty V* + V*, with some sequence-to-token function where input sequence (I11 (n) we have that
TT( n.)) = ((1,2))
Observe that sequence-to-token function f can be used ruto-regressively to generate tokens from some initial sequence (zı, vn) via the following update rule:
Ints = [XI,,.., Iatis-1))
(2)
This can also be viewed as special case of the causal model, where the input sequence is chosen that
T2,, kn) = (I2, .,, Fn41).
Hence, if we are trying to learn a causal or anto-regressive model, it suffices to learn the sequence function that generates it. Thus in this paper, we focus on the type of sequence functions that encoders versus decoders can learn and express.
Encoders and Decoders. We will use the letters & and D respectively refer encoders and decoders. In this paper, both models refer to variants of the Transformer architecture introduced in Vaswani et al. (2017,, where the only difference lies in the masking used the attention scores (decoder uses causal mask while encoder allows full attention, as illustrated in Figure T.
The model size of a Transformer is determined by two parameters:
3

---

Published in Transactions on Machine Learning Research (11/2025)
L: number of Transformer blocks.
D: embedding dimension.
As Transformers are sequence-lo-sequeen maps, we will use subscript nolation where T(r,,..., En), denoles the z'th value in the output sequence. We also allow our models the option to use positional embeddings. Tilde-notation i.e. & and DD will denote models that do not use positional embeddings. For token embeddings 21 21,.., In and positional embeddings p1..... Pu.
E Fn) = E(r) + Pl,..., Zn + pn).
In our experiments, we will use encoder and decoder models that have access to trainable positional embed- dings.
Encoder and Decoders as Causal Models. Given encoder & and decoder D, we can associate them with sequence-to-token functions as follows:
fe (I1,...,, In) H E(I,,..., Fnln
fo (21,..., In) + D(r1...... TT., In)n.
We then have To and To as the causal models of & and D when used as sequence functions fe and fo respectively]
Under this characterization, we make two observations. Firstly, we can view Te explicit and necessary way to introduce causality to the encoder since there is nothing implicit to the encoder that forces causality, Secondly, in juxtaposition to the previous statement, the causal model To is exactly equivalent to just using D, that is To = D. This is because enforces causality implicitly via the attention mask (see Appendix [A.2 for formal proof). Therefore, the explicit enforcement becomes redundant. To coneretely illustrate these two observations we additionally provide full derivation of the computation in toy two-layer example comparing difference between encoder and decoder in Appendix A.4
4 Expressive Power of Encoder-only vs. Decoder-only Transformers
learn causal functions (defined as causal model in preliminary) using either encoders and decoders, the natural question to ask is how the expressive power of each model is related, i.e. can the encoder express more causal functions than decoder of the same model size? Or perhaps they express the exact same class of causal functions? Towards answering this question, one trivial observation is that one-layer decoders and encoders are equivalent (formal proof in Appendix [A.3) which directly implies the existence of causal functions that both architecture can model exactly.
Given that
Now, what about causal functions that decoder can model but not encoder, vice versa that encoder can model but not decoder? These functions exist too, we show in the following two theorems:
Thcorem 4.1. For any L 2 and D 2 1, there crists position-free decoder D that has L-lagers and embedding dimension D, such that for any encoder E, there erists some inpul sequence (21, wilh 21, E RD, and T=(21, x2....) # Te Te(11.22.....
Theorem 4.2. For any L 2 2 and D 2 1, there exists a position-free encoder E that has L-layers and embedding dimension D, such that for any decoder D with positional embeddings salisfying pr # P2, there exists some input sequence (21,,2,.. with I1, 22. E RD, and T2(=1,T2,.... * TD I2.
The above two theorems are existential in nature. Informally, Theorem 4.1 says that if we consider causal model defined over the entirety of R its vocabulary, we can find some decoder, for which any encoder will differ from it on some input sequence. Theorem 4.2 makes a similar (albeit weaker statement) in the
"To be fully consistent with notation equation notation and use Te and To for sake of simplicity. Heee causal function refers sequence sequence-t-ssqqeee to-suuence function where the outputs only determined by current and previous inputs, ie. F(11, P2, -., gn) ) only depends on æ1, 22, 3i, not zy for any j i.
should denote them Tye and Trp respectivcly. However we abuse
4

---

Published in Transactions on Machine Learning Research (11/2025)
other direction; namely the existence of causal function computable by encoder, but not by any decoder that uses "non-trivial" positional embeddings (e.g. embeddings for different positions are unique). Detailed proof of both theorems are deferred to Appendix A
Of course, the setting and assumptions of the above two statements are not necessarily very realistic. For one; they focus on general class of causal models rather than only auto-regressive ones. The assumption of unbounded domain is also not realistic as in practice decoders are trained and used over finite domain of tokens, each with some fixed embeddings. And specific to Theorem [.2)] claim is made about decoders that do not positional embeddings. But despite the limitations, these theorems give an indication that the expressive power of encoder and decoder model are different - despite the almost identical descrip- tion modulo the attention mask. Changing the mask on the attention scores causes significant changes to the properties of the model. Thus, in the following sections we propose an auto-regressive tasks and run experiments comparing encoders and decoders that corroborates this view.
While the previous theorems show that ENTP and decoder-only Transformers can express different causal functions exactly, they do not address their abilities to approximate functions. In practice, models only need to approximate functions, not represent them exactly. Under this relaxed setting, ENTP can replicate causal masking by augmenting their queries and keys, effectively simulating decoder.
Given the decoder's queries and keys, Q = [m, -., mm]" and K = [k1, kn, the causal mask can replicated in a noncausal attention mechanism by augmenting the queries and keys. For a sequence of length 4, the queries and keys are augmented as follows:
q
x
KT
0
0
Q
%
92
T
0
00
K
K7
K
0
1
0
0
0
0
(4)
94
T
0
KT
1
1
0
Multiplying these, obtain:
of Ki
-00
93 kn
43 1:2
QKT
(5)
93 k1
43 k2
43 Ka
94
94 k2
41
hy
4 ka
which is exactly equivalent to applying causal attention. Functionally, -oo is a sufficiently large negative constant.
For any sequence length n, given orthogonal basis 01 a2...., Anz
q. =
9i
and
=
-000;
== a4
so that
The Rig if i21
of kg
if i<j
Furthermore, from the Johnson-Linndenstrauss lemma, it. possible to approximate these augmented keys and queries using embedding extensions of only Ollggn) dimension, by using a basis that is approximately orthogonal.
Thus, provided that positional information is accurately propagated through the Transformer via skip con- nections, an encoder can effectively replicate causal attention.
Finding While ENTP and decoder-only Transformers express distinct sets of causal functions exactly, encoders can approzimale any causal, function that a decoder can compule.
5

---

Published in Transactions on Machine Learning Research (11/2025)
As will be shown in Section 6.2 the inverse does not hold: there exist some ENTP models that decoder-only Transformers cannot approximate.
5 Time and Space Complexity Comparisons
Inspired by the different computational models of encoder-only and decoder-only Transformers, we character- ize the causal sequence functions learnable by encoders and decoders based on their required computational complexity. We give an informal comparison of encoders and decoders terms their required time and space complexities
both over the entire sequence and for each additional token. We propose Count3, which is closely related to Match3 (Sanford et al. 2024b), to highlight the "gap" between the complexity of encoders and decoders. Count3 is feasible for an encoder but challenging for a decoder due to its limited computation complexity.
Time Complexity Comparison. Decoder-only Transformers, using KV-Cache, take O(n) time to gener- ale each loken, and (n²) time lo generate an entire sequence. Because an ENTP has to compute the entire attention matrix for every token, takes O(n²) time generate each token. Thus, it takes O time generate the entire sequence. While this implies that ENTP is more compute-intensive (i.e., ENTP will be slower than dncoder-only Transformer), this also implies that ENTP can express more compute-intensive functions than decoders. Specifically, since the total amount of compute that decoders use for generating tokens is Onn²), they cannot run any algorithm whose runtime is w(n²) (strictly greater than quadratic time).
Space Complexity Comparison. Both encoder-only and dccoder-only use O()) space complexity generate an entire sequence. Although the standard implementation of attention uses O(n²) space, attention can be implemented using only (n) space. For details of algorithmic implementation of attention using constant space per token, refer to Algorithm Din in the appendix. Thus, we need more detailed approach to find a difference between the space complexity of the two models.
Towards this end, we classify memory used for the computation over the current token as either precomputed or additional. Precomputed memory stores values from computation over past tokens. Values stored in precomputed memory persist, and are used for computation over current and future tokens, e.g. the keys and values of previous tokens for a decoder. Additional memory stores values that depend the current token, e.g. keys and values of the current token.
When generating the nth token, a decoder uses ((n) precomputed memory to store keys and values of previous tokens and 0(1) additional memory to compute results over the current token. An encoder computes everything from scratch for each token, so uses (n)) additional memory and no precomputed memory. Under this view, there a space complexity gap between encoder and decoder.
Table 1: Complexity for next-token inference.
Complexity
Encodcr-only
Decoder-only
Additional Time Complexity
O(nDDL
O(nDL)
Precomputed Space Complexity
N/A
O(nDL)
Additional Space Complexity
O(nD)
O(D)
Most of our complexity analysis focuses on Transformers with fixed sizes, so we primarily consider complexity with respect to the sequence length n. However, we also account for the embedding dimension D and the number of layers L in Table 1 Both encoder-only and decoder-only Transformers use O(LD) time because the allention operalion is performed O(L) times, and computing each query, key, and value vector is O(D). In the case of multi-head attention, we assume D = hd, where h the number heads and d is the dimension of the query, key, and value voctors. decoder uses O(nhdL) O(nDL) procomputed space because it stores nhL query, key, and value d-dimensional vectors. Both encoders and decoders use O(D) additional space for current token's embedding vector and we specifically note that there is dependence on L.

---

Published in Transactions on Machine Learning Research (11/2025)
Transformer do computation sequentially the layer (i.e. all the additional computation required for layer & is done before all the additional computation required for layer + 1). Thus, we can do the computation over L layers using ODD space by overwriting computation over previous layers.
6 Task- Task-Specific Analysis with Count3
Consider the sequence function that maps an input sequence of positive integers T1, J2, ...... 2n to the number of pairs 2, where the modulo-n sum of 24,27 and In is equal to O. More formally,
Count3 [1, I2,..., = ((i.)) E [n] in + By + In = 0 (mod n)} (mod n).
(6)
3ount3 an augmented version of Match3 (Sanford et al.) 2024b). As shown in Sanford et al. (2024b) the triple-wise relationships, used in both Match3 and Count3, are difficult for Transformers represent, because of the pairwise nature of sell-attention.
Note that there exists algorithms that compute Count3 some length-n input sequence Z1, 22,22,... In in either (n²) time and ((1) space or in O(n) time and ((n) space. See Algorithm 2 and Algorithm 3 in Appendix E for exact pseudocode implementations. In brief, Algorithm 2 iterates through all n² pairs checking if they meet the modulo-n sum requirement. Algorithm 3 uses the fact that I2 + Iy + In = 0 (mod n) is equivalent to I; + xn = - (mod n). In two linear passes, counts each -Ig (mod n) and stores each count table, then sums the values in the table for each 2, + In (mod n). Now, given these two algorithms, make the following conjecture:
Conjecture 6.1. Given an algorithm A that computes Count3(I1, #2, ... In), at least one of the following must hold true:
(i) A requires (nn²) time with access to Fn
(it) A requires Mn)) space storing values unique n.
This conjecture seems plausible given that both Algorithm 2 and Algorithm 3 which we consider to optimal, adhere to it. Algorithm uses Onn²) time after accessing on (line of Algorithm 2 and Algorithm 3 requires (nn) memory, where the stored values are function of (line of Algorithm
6.1 Expressivity of Transformers on Count3
We analyze the expressivity of decoder-only Transformers and ENTP on Count3. From Conjecture 6.1 we have the following lemma:
Lemma 6.2. Given that Conjecture
6.1 holds and assuming O(logn)) precision, any decoder-only Trans- former with fixed embedding dimension satisfying D(I1,.... Immm (ount for all sequences of length m I n must have L = ((n)..
Proof. Let. D be a decoder with L layers and embedding dimension D satislying D(ri,..,, (ou Fm)) for all sequences of length m I n. We can use D as an algorithm to compute Count3(21,...,, Tx), by outputting D(2 on input (z1,..., In). Thus either condition or of Conjecture 6.1 must hold when D computes the output sequence over (II,...,
Case 1: ii) is true. In this case D requires 2(n2) time with access to Rny i.e. D uses 2(n²) time for the last token. From Table I we know that D uses O(nLD) time for each token. Thus condition is true only if we have that nLD ((n²). Since D is fixed, it follows that L R(n).
3O(logn) n) precision is required for Lemma 6.2 but included be consistent with Lemma

---

Published in Transactions on Machine Learning Research (11/2025)
Seed
Auto-regressively generated sequence using Count3
Full Sequence 41, 40, 44, 26, 38, 34, 44, 0, 58, 46, 10, 10, 24, 49, 6.
8, 10, 18, 12, 1,
12. 18, 4, 20, 13, 2, 6, 18, 1, 16, 22, 33, 30, 6, 2, 21, 22, 1, 24, 35, 42, 12, 16, 27, 40, 15, 34, 48, 16, 40, 15, 16, 17, 14, 20, 58, 60, 8]
Example of 17th element
6 pairs:
(x2, X7 (x7, X2
( X3,, X12 ) (x12+
X12 X16 (X16. X12
(41 49) mod =
(46 + 49) mod (1 46 mod 16
Figure 2: An example of sequence used in Count3 experiment.
(ii is truc. In this case, D requires (()) space storing values unique to n. Because decoders are causal, we have D(r Tn); Count3(r1,...,. 24) for all i E [n]. Then since assume i is true, computing D(r En); requires (() space for each i E [n]. Furthermore by the uniqueness assumption of [ii] for A j. the values stored when computing Count3 (..... are different from the values stored when Since decoders are causal, the space used to compute D(z1,..., In); cannot overwrillen when computing D(.),...,,nn) for j > Hence, when D computes (o, it uses 111i) space to compute Count 2z), for each E [n]. Thus, D uses Ω (Eeemy) 1) 22(2)) space to compute Count (fx) From Table [ we know that D uses O(nLD) space for the entire sequence. Then nLD (2(")). Since D is fixed, it follows that == 9(n).
Case 2:
computing Count3(21,.....
Finally, as L = (2)) is necessary condition for both conditions and
ii Theorem
6.2 follows.
Lemma 6.3. Assuming Olog precision, there erists an encoder & with L O(1) and 0(1) such (oi..t for all sequences of length m n.
that (x11 Fm)
Proof of Lemma 6.3 is Appendix A.7
Remark 6.4. With linear fhain-of-thought (generating O(n) tokens before answering), decoder would be able to perform Count3. We provide RASE (Weiss et al. 2021) program, Algorithm 6 to demonstrate
this.
6.2 Implications of Lemma 6.2 for Decoder Approximation of ENTP
Lemma 6.2 addresses the exact computation of Count3. Many continuous Transformer realizations can inter- polate such function. This is in contrast to Section 4 which focuses on exact replication and approximation of continuous functions mapping sequences of vectors in Rd.
If no decoder-based language model can exactly replicate a given ENTP-based language model (i.e., produce outputs whose argmax predictions match), then there must also be a limit on how closely a decoder can approximate its output embeddings, assuming there a nontrivial gap between the largest and second largest logit values (as observed for our ENTP models on the Count3 task, which achieve near-zero loss in Figure 3 Thus, combining Lemma 6.2 with the observation above, decoder cannot approximate arbitrarily well an ENTP model that successfully solves Count3, without its size scaling with sequence length.
6.3 Count3 Experiments
We train small decoder-only and encoder-only Transformers on auto-rogressive sequences generated from Equation G To generate unique sequences, we start each sequence with a seed containing random integers between 0 and 63, Then we extend the sequence 64 integers using Equation (6) (see Figure 2 Sceds are generated randomly during training and evaluation. With 64 x 1.16 x 1077 possible sceds, the chance of significant duplication among the 1.28 107 seeds used for training and evaluation is negligible.
We d' a.s Zen
5 RASP WWlss al. 2021) programming language that descrihes Transformer computations, mapping attention and feed- forw-for computation into simple primitives.
8

---

Published in Transactions on Machine Learning Research (11/2025)
Consequently, the reported results effectively correspond to "test" loss and accuracy. The seed portion of the sequence not used to compute the loss during training, so the model was only trained on the deterministic part of the sequence.
As shown in Figure g the decoder-only Transformers demonstrate some ability to learn patterns related to the distribution of numbers Count3 sequences, but they completely fail learn the task. In contrast, the encoder successfully learns the task with near-perfect accuracy.
We also evaluated Prefix decoder-only models (Raffel et al. 2020 Wu et al. 2021), which perform non- causal attention for the prefix portion of the sequence. We used the same experimental setup, and set the 16-integer seed as the prefix. As shown in Figure[3 3 while the Prefix decoder-only model slightly outperforms the decoder-only model, it also fails to learn the triplet counting task. This suggests that incorporating full attention over parts the sequence in a decoder-only model is insufficient for solving tasks with Count3-level complexity.
To demonstrate that ENTP is effective for larger pre-trained models, fine-tuned BERT (Devlin el. al. 2019 0 using the ENTP approach under the same experimental conditions. As shown in Figure 3 BERT combined with ENTP successfully learned triplet counting. Notably, BERT is pro-trained and larger compared to the medium transformer, it converged more quickly and achieves higher accuracy.
1.00
Medium Decoder
Medium Decoder
3
Sequence accuracy
Medium Prefix
Medium Prefix
Medium ENTP
0.75
Medium ENTP
Loss
BERT ENTP
BERT + ENTP
0.50
1
0.25
0
0.00
20D(X)
40000
GUD(X
80000
100000
120000
20000
40000 Training step
60000 100000 120000
80000
Training step
Figure 3: Training loss (left) and sequence accuracy curve (right) for the Count3. ENTP success- fully learns to perform the Count3 task, but the decoder-only Transformers and prefix Transformers struggle to learn it.
1.ama3 Training Loss
Lioma3 8B Sequence Accuracy
GPT 4e Training Loss
GPT de Sequence-ecuaay
Sequeace accuraicy
Sequence accuracy
0:11
0.6
0.5
0:1
0.2
0.2
5000 10000)
15000
20000 25000
30000
0
5000
1000 15900 20000 2000 50030
2000
4060)
6993
1000
18000
2000
4000
4000
1000
19000
Training step
Training step
Training stop
Training step
(a) Llama3-8B fine-tuning results
(b) GPT-4o fine-tuning results
Figure 4: Results of LLM fine-tuning on Count3. Decoder-only Transformer, even at large scales, fail efficiently learn the Count3 task.
To investigate the performance of decoder-only large language models (LLMs) on the Count3 task, we fine- tune Llama-3 (Dubey al. 2024 and GPT-4o (Achiam et al. 2023) using sequences 64 integers introduced previously. To enable the LLMs to leverage their knowledge, we also include the code for Algorithm 2 in the
6ERT is encoder-only Transformer trained using the masked language modeling objective.
9

---

Published in Transactions on Machine Learning Research (11/2025)
prompt, asking the models to provide the result after executing the code (sce Table 5 for the full prompt). As shown in Figure 1 the LLMs struggle with the Count3 task, which is consistent with our small-scale experiment. It demonstrates that the suggested characteristics of causal decoder-only models hold true even at large scales. We provide the validation of the prompt design used, as well as details about the LLM fine-luning, the Appendix C.1
Finally, we remark that Count3 sequences have low Kolmogorov complexity, meaning the smallest program generating them is upper bounded by the six-line Algorithm 2 However, as shown in Theorem 6.2 and the experiments above, no decoder-only Transformer, regardless of size, can efficiently learn the task.
Finding 2: ENTP can easily learn Count3, but large decoder-only Transformers cannot.
6.4 Similar Function Learnable by Decoder
Motivated by the question of how we need to change Count3 so that it can be learned by a decoder, we examine a modified version of Match3 (Sanford et al. 2024b).
(1.)) x2 2, ====00 =0 (mod 128)
Match3' 22, xn).,, =
otherwise
There are several key differences between Count3 and Match3': (1) Match3' uses a fixed modulus, whereas Count3 employs the sequence length as the modulus. This simplifies the decoder's task, as the modulus remains constant across all tokens, enabling reuse of intermediate values from previous tokens; (2) Match3' operates triplets (z1, rather than ZJ. By using 21 instead of 2n, it becomes easier for the decoder since 21 remains unchanged for different tokens, facilitating the reuse of intermediate values across tokens; (3) Match3' checks for the existence of a condition rather than counting occurrences. Counting is challenging to implement within the attention mechanism without scaling values by the sequence length. Due to the causal mask, scaling value vectors by sequence length not straightforward.
We provide RASP [Weiss Match3' (11,, .., 22, -. ) for sequences of any length, assuming O(logn) precision. We train small Trans- formers to verify that both decoders and encoders perform Match3', and find that both models can perform Match3' with high accuracy.
al.] 2021) program, Algorithm 5 that satisfics D(x1, 32, 22,,.., Fn)n
Table 2: Match3' performance.
Model
Min Loss
Token Accuracy
Full Sequence Accuracy
Medium Decoder (6 layer)
0.0001
99.99%
99.92%
Medium Encoder (6 layer)
0.0016
99.97%
99.50%
7
Experimental Results for Small-Scale Language Modeling Tasks
Scaling up ENTP to large models remains challenging, but it can still be tested effectively at limited scales on simple lasks. To assess its capabilities, we train ENTP models on small yel representative language modeling benchmarks. These tasks include arithmetic reasoning (Lee et al.
2023 McLeish et al. 2024 Zhou et al.
2024), in-context learning with synthetic data (Garg al.) 2022
Bai al. 2023 Ding al. 2024). and
language modeling on small datasets (Polo al.) [2024] Sinha et al.) 2019). By focusing on these controlled
experiments, evaluate ENTP's potential while keeping computational demands manageable.
10

---

Published in Transactions on Machine Learning Research (11/2025)
1.00
Decoder ENTP
Decoder
Test Error Rate
Test Error Rate
ENTP
0.75
10"1
0.50
0.25
0.00
1750
2400
1050
1000
10000
1900
2000
1010
13
14
Number of Training Examples
Number of Digits (> 10 OOD)
Figure 5:
Addition Sample Complexity. The Figure 6: Addition Length Generalization. The train set has mumbers up to 10 digits, and the test set has up 15.
train and test datasets include numbers with up digits.
1.2
1.2
Decoder Decyder-only
Decoder-one onnl Encoder-only
Squared error
1.0
Squared error
1.0
Encoder-only
0.6
0.6
0.4
0.4
0.2
0.2
0.0
0.0
15
25
35
25
In-context examples
In-context examples
(a) Linear Regression
(b) Sparse Linear Regression
Figure 7:
Results of in-context learning experiment. The encoder-only models demonstrate superior performance across both function classes compared to the decoder-only models.
7.1
Generalization on Addition
We test the sample complexity and length generalization capabilities of decoders and encoders using addition tasks. We use the reversed addition format ($123+456-975$) from Lee et al. (2023. We find that encoders exhibit lower sample complexity compared to decoders, as seen in Figure meaning they require fewer training examples to achieve similar performance. Additionally, encoders demonstrate superior ability to generalize to longer sequences, as shown Figure Appendix C.3
We provide more experimental details and results in
ENTP achieves superior generalization compared to decoder-only Transformers both in-distribution and oui-of-distrruulion dala.
Finding 3:
7.2 In- Conntet Learning
We consider the problem of learning function class F using in-context example (Garg et al. 2022). In this problem, a function e F is sampled from a distribution Dy, and a sequence of random inputs is sampled i...d from Dx, forming a prompt. P (æ1, (x1), x2, (zz2),..., N (IN)). The objective is for the model
to in-context learn the function f from the prompt P and predict f(Equery) for a new input Zquery.
We examine two types of function classes: linear function and sparse linear function. For both function classes, sample Ha from Gaussian distribution and utilize the squared error as loss function.
11

---

Published in Transactions on Machine Learning Research (11/2025)
We present the in-context learning results according to the number of in-context examples for each function class in Figure 7 ENTP demonstrates superior performance compared to the decoder-only models in in- context learning for both function classes. A detailed description of each function class, along with additional experimental results for the non-lincar function classes, is provided in the Appendix C.2
Finding 4:
For in-conterl learniing, ENTP shows compelitive performance compared to decoders.
7.3 Natural Language Tasks
We train Transformer models on the OpenWebText dataset Gokaslan et al. 2019 an open-source repli- cation of WebText used for GPT-2 training (Radford et al. 2019), using next-token prediction objective, We conducted OpenWebText training of ENTP models with two different seeds. We use medium models, described in Table 0 and hyperparameters from Table slightly outperforms the decoder-only Transformer.
As shown in Table 3 the encoder-only Transformer
To assess commonsense reasoning, we use the TinyWinoGramt benchmark (Polo al. 2024). which tests pronoun resolution. After pretraining on OpenWebTexx, both models undergo zero-shot evaluation on this benchmark.
We further evaluate the models on NLP classification task using CLUTRR (Sinha et al. 2019) which requires identifying familial relationships from text. After fine-tuning on CLUTRR, both models are tested on a holdout set. We randomly select 10,000 examples for the training set and conduct each experiment using three different random seeds.
As shown in Table 4 ENTP achieves higher accuracy than the decoder-only model on both the TinyWino. Grande and CLUTRR tasks, demonstrating its potential for diverse natural language tasks.
Minimum values of training and validation loss, as well perplexity, for decoder-only and encoder- only Transformers on the OpenWeb Text dataset. Results are averaged over two different random sceds. We report results for the individual training runs in Table 7
Table 3:
Model
Train Loss
Validation Loss
Train Perplexity
Validation Perplexity
Decoder-only
4.689 + 0.006
4.701 0.005
108.7 = 0.603
110.0 + 0.496
Encoder-only
4.636 + 0.008
4.643 + 0.008
103.1 + 0.795
103.8 + 0.786
Table 4: The performance of decoder-only model and ENTP on the Tiny WinoGrade and CLUTRR bench- marks.
Benchmark
Decoder-only
Eucoder-only (ENTP)
TinyWnnGraande Error Rate
43.5 0.5 %
38.0 + 1.0 %
CLUTRR Error Rate
0.9 + 0.12 %
0.5 - 0.03 %
Finding 5: ENTP performs better than decoder-only models on nerl-token prediction based lan- guage modeling, leading to superior performance on downstream natural language tasks.
8 Discussion
In this work, we present thcoretical and novel experimental results suggesting that, assuming compute is unlimited, decoder-only Transformers are not the ideal model for sequence modeling. We show that ENTP is more expressive without compromising generalization. Using Theorem 4.1 and 4.2 we find that the classes
12

---

Published in Transactions on Machine Learning Research (11/2025)
of functions encoder-only and decoder-only Transformers can exactly learn are different. We introduce the Count3 task and demonstrate, both theoretically and experimentally, that while ENTP can perform it easily, decoders cannot. We also find that encoders outperform decoders on various auto-regressive tasks, including length generalization and in-context learning.
Despite its advantages, ENTP currently computationally inefficient for practical deployment. However, it is a valuable architecture for further study, as can provide deeper insights into the fundamental workings of Transformers. By understanding why ENTP exhibits superior expressiveness and generalization, may be able to leverage these insights to develop improved next-generation architectures for language models.
A promising future direction is developing compute-efiiiien ENTP variant that retains its strengths while narrowing the efficiency gap with decoders. Achieving this balance could lead to models that surpass existing architectures in both performance and scalability, making it a valuable area for further research.
Acknowledgments
The work of Kangwook Lee is supported in part by NSF CAREER Award CCF-2339978, Amazon Research Award, and a grant from FuriosaAI. Dacwon Chac was supported by Hyundai Motor Chung Mong-Koo Foundation.
References
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Tlge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint trXiv:2303.088 08774, 2023.
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers statisticians: Provable in- context learning with in-context algorithm selection. In Thirtg-seventh Conference on Neural Information Processing Systems, 2023. URL
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Nee- lakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Berbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christo pher Berner, Sam McCandlish, Alec Radford, Tlya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pp. 1877 1901. Curran Associates, Inc., 2020.
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1-113, 2023.
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Yunxuan Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahuna, et al. Scaling instruction-finetueed language models. Journal of Machine Learning Research, 25(70):1-53, 2024.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova, Bert: Pre-training of deep bidirectional transformers for language understanding, 2019. URL httpt:ttts:::xxi// wtwp://www...gg///////.... 04805
Nan Ding, Tomer Levinboim, Jialin Wu, Sebastian Goodman, and Radu Soricut. CausalL. is not optimal for in-context learning, In The Twelfth International Conference on Learning Representations, 2024.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21788 2024.
Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant. What can transformers learn in-context? case study of simple function classes. In Advances in Neural Information Processing Systems, 2022.
13

---

Published in Transactions on Machine Learning Research (11/2025)
Angeliki Giannou, Shashank Rajput, Jy- Yo-Y Sohn, Kangwook Lee, Jason D. Lee, and Dimitris Papailiopon- los. Looped transformers as programmable computers. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th Interna- tional Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp.
11398 11442. PMER, 23 29 Jul 2023. URL
mlr, press/v202/ http///iinnnnnaaa..
Aaron Gokaslan, Vanya Cohen, Ellie Pavlick, and Stefanie Tellex. Openwebtext corpus.
http://
www.oon007.gthuu..o. httphhhww....ppppaaaaaerttrppppp 2019.
Edward J Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations, 2022.
Nayoung Lee, Kartik Sreenivasan, Jason D Lee, Kangwook Lee, and Dimitris Papailiopoulos. Teaching arithmetic to small transformers. In The Twelfth International Conference on Learning Representations, 2023.
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdel rahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. Bart: Denoising seaeence-to-sqqeeeee pre-training for natural language generation, translation, and comprehension. In Annual Meeting of the Association for Computational Linguistics, 2019.
Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2002. 12875, 2024.
Sean McLeish, Arpit Bansal, Alex Stein, Neel Jain, John Kirchenbauer, Brian R. Bartoldson, Bhavya Kailkhura, Abhinav Bhatele, Jonas Gciping, Avi Schwarzschild, and Tom Goldstein. Transformers can do arithmetic with the right embeddings, 2024. URL /tttps://arxii.orr//bbass
17399
William Merrill and Ashish Sabharwal. logic for expressing org-precision transformers. Advances Neural Information Processing Systems, 36, 2024.
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.
Ajay Patel, Bryan Li, Mohammad Sadegh Rasooli, Noah Constant, Colin Raffel, and Chris Callison-Burch. Bidirectional language models are also few-shot learners, 2023. URL httpa/:///xxivvo/r///o org/ abs//299. 14500
Jorge Pérez, Pablo Barceló, and Javier Marinkovic. Attention is turing-complete. Journal of Machine Learning Research, 22(75):1 35, 2021.
Felipe Maia Polo, Lucas Weber, Leshem Choshen, Yuekai Sun, Gongjun Xu, and Mikhail Yurochkin. tiny- benchmarks: evaluating LLMs with fewer examples. In Forty-first International Conference on Machine Learning, 2024. URL
Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and 1lya Sutskever. Language models are unsupervised multitask learners. 2019. URL http:////hpp..emmmmtcccccchlaaa org/Cor)pssDD::6005553
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lec, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21 (144) 2020.
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. One-layer transformers fail to solve the induction heads task. arxiv preprint or Xiv::22008. 14332, 2024a.
Clayton Sanford, Daniel J Hsu, and Matus Telgarsky. Representational strengths and limitations of trans- formers. Advances in Neural Information Processing Systems, 36, 2024b.
14

---

Published in Transactions on Machine Learning Research (11/2025)
Koustuv Sinha, Shagun Sodhani, Jin Dong, Joelle Pineau, and William L. Hamilton. CLUTRR: A diagnostic benchmark for inductive reasoning from text. CoRR, abs/1908.06177 06177, 2019. URL http://arxii.orrr 061717
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, F. ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnelt (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Thomas Wang, Adam Roberts, Daniel Hesslow, Teven Le Scao, Hyung Won Chung, Iz Beltagy, Julien Launay, and Colin Raffel. What language model architecture and pretraining objective works best for zero-shot generalization? In International Conference on Machine Learning, pp. 22964 22984. PMLR, 2022.
Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In International Conference on Machine Learning, pp. 11080-11090 PMLR, 2021.
Shaohua Wu, Xudong Zhao, Tong Yu, Rongguo Zhang, Chong Shen, Hongli Liu, Feng Li, Hong Zhu, Jiangang Luo, Liang Xu, et al. Yuan 1.0: Large-scale pre-trained language model zero-shot and few-shot learning. arXiv preprint ar arXic:2110.04799 2021.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are transform- ers universal approximators eqquence-to-sqquene functions? In International Conference on Learning Representations, 2020.
Hattie Zhou, Arwen Bradley, Etai Littwin, Noam Razin, Omid Saremi, Joshua M. Susskind, Samy Bengio, and Preetum Nakkiran. What algorithms can transformers learn? study in length generalization. In The Twelfth International Conference on Learning Representations, 2024.
15

---

Published in Transactions on Machine Learning Research (11/2025)
A Notation and Deferred Proofs
A.1 Notation
E, D: Encoder/Decoder with positional embeddings.
ε, D: Encodar/Decoder without positional embeddings (with same model weights as &, D) (which
call position free).
Ia number of Transformer blocks.
D: embedding dimension.
Ps: The i'th positional embedding where Ps E RDD
W W/rkyv The weight matrix of the Query, Key and Value respectively of the i'th attention block.
The identity matrix.
0: The zero matrix.
(m) 22, Ta.-.. ): A sequence of values/tokens.
Te (2), 22, Va. ..... ) (f( (211, rs)3...
For convention, we will use bold capital letters X to denote matrices, and unbold lowercase letters ar denote vectors.
For theorem 411 and theorem 4.2 model of Transformers will use single-head attention and assume the dimension of the Query and Key are equal to the embedding dimension D. We also omit layer normalization and scaling of attention scores by 1/vD.
A.2 To D
Proof. The main obscrvation is that the the MLP layers of decoder are clement-wiset and the attention layers of a decoder are causal (i.e. the contextual embedding of the i'th token computed only using the tokens j & i). We thus have that
D(E Fa. (D.1,...,32:)
for any i E [n]. As a result,
Dir Di............... sa); D(I
fo(
(21. 21. Di...., 2n)
for all i [m], i.c D(o
A.3 One-layer Encoder and Decoder are Equivalent
Proof. Let. D and & have the same parameters. Then the query key, and value vectors for the allention layer (denoted qss k; v, for each F, respectively) will be the same for both models.
For one-layer decoder: D(I,,..., vn); = MI.P E Softmax(g;; ky)o))
For one-layer encoder: E(I1,..,, ML. Σ Softmax(q,,;;))
If n, then D(1 ... Fn)i (.)), Thus, To (x11 "o..,,,....,. vn) Tel Te( 02,...,
7
16

---

Published in Transactions on Machine Learning Research (11/2025)
A.4 Illustrative Example of Computation over Two Layer Encoder and Decoder
Setup. We compare Iwo-layer Transformer with single head self-allention blocks only no MLPs, no residual connections, no layer norms, and no output projections on a length-2 input (21, For token attending to token j in layer l, define the score
2 = (WQ) (1-1), 24
W 1)
Here ( = z; are inputs, and z; are the outputs of layer f. For an encoder, each token may attend to both positions (1 and 2) in every layer. For a decoder, loken may attend only to itself, while token 2 may attend to both positions (1 and 2) in every layer.
Layer computations. Each layer applies only attention with values W Below write the length-2 updates explicitly (i.e., the computation when we are trying to generate the output corresponding to the second Loken in our causal model), expanding the softmax weights directly.
Decoder:
(1) w X1,
(1) e 2 W. v 11 + 22 w
22
e 22
(2) w (1) W/ w (1)
21
11
I1,
(
W (2) (1)
(2)
(2) e
2
V 11 + 2
v
22
2 + 2-12
Encoder:
1 W (1)
11 + 1 W (1)
(1)
(1)
22
31
e + 4-42
2
W 11 + 242 ( 22
(1)
11)
2 + 2-42
W 2
(2)
W (2)
(1)
(2)
1-11
V
41
+ 1-42
W (2) x
(1)
2 W (2) (1)
22 2
(2)
02
2-11
Takeaway. In the decoder, causality is implicit: ( depends only on 21 for all E, so previously computed keys/valuee values for the first position can be reused when producing the output corresponding to position two later layers. In the encoder, xi to the second token. In other words, we explicitly enforces causality by recomputing each of the earlier hidden representations when generating a new token.
(1) depends on both I and x2 when used to compute the output corresponding
A.5 Proof of theorem
Proof. We first provide a construction for D. For the attention-blocs of the first two layers, we use the same weight matrices. Namely, we set W K = W = W/ = W = and W = W = For every other attention block, we set them to the constant zero function by setting W Vy = 0 for i 2 3. We similarly set the weights and biases of every MLP block to zero. Thus, essence D just two duplicate attention blocks stacked on top of each other with skip connection after each attention block.
17

---

Published in Transactions on Machine Learning Research (11/2025)
Now consider three arbitrary vectors ø1, 22,22,2 23 IR' and its corresponding sequence (#1, (2,, Let us first compute the output of D on (21, 13). The first attention block and skip connection will map the input soquence to the sequence
21 + 22 21 + 2/2 + F3
2x +
2
3
The second attention block and skip connection will then map to the following:
731 + 9x2 23 + 173/ + 32.3
421
4
18
Our first observation from this mapping is that there clearly exists Tι, T2, 43 E RR such that D(21, #3)3 # D(2,, 03)3. Our second observation is that
7 + 922
4r
31 = T2
4
which follows from simplifying the left hand equation.
Now, let us for sake of contradiction assume the existence of some encoder & such that Te exactly replicates D on every imput sequence. We first claim that the first two positional embeddings P1.P2 of & must differ. This follows by our first observation and thus the requirement that only happen if p1 # p2 due to the permutation invariance of encoders when there are positional embeddings. Now as Pı & P2, there exists vectors y1, U2, E RD such that y1 * 1/2 and + P1 8/ + P2 c. It follows immediately that
+ E(2,, T3)3
which
E(y1)1
E(v1 + P1)1
E(c)1
E(c,c)2
ε(vI + P1, + P2)2
(21,
But since Y1 # y2, by the second observation we made, must be that D(y1) # D(v1. Since we assumed that Ts exactly replicates D on every input sequence, it thus follows that E(11) # E(v1, - a contradiction. Hence, no such encoder & exists, which directly implies that we can always find some sequence (z1, .2...) where D(I,, * (2,.........
A.6 Proof of theorem 4.2
Proof. We first provide a construction for E. For the attention-block of the first two layers, we use the same weight matrices. Namely, we set W = W W = W W W = For every other attention block, we set them to the constant zero function by setting W = 0 for i 2 3. We similarly set the weights and biases of every MLP block to zero. Thus, in essence & is just two duplicate attention blocks stacked top of each other with a skip connection after each attention block.
Now consider two arbitrary vectors 21,42 E RRD. and its corresponding sequence (01, x2). A brief inspection will reveal that
x2)) = (4x1, 0z1 + Bx2),
where 3 > 0.
Next, we assume the existence of some D where p1 * P2 and exactly replicates E. We fix x1 0 and let
22 = P1 P2. Observe that 32 # 0 as pr # p2. It follows that there is some constant vector R where
D(z1, = D(I1 + PP. + P2)
D(p1,PI)
(c,
18

---

Published in Transactions on Machine Learning Research (11/2025)
Now from equation have that (2), (0,8rz) for some 3 > 0. As 22 0, it follows that fxg # and hence (0, (r2)) not constant sequence - contradicting the output of the decoder. Hence, no D where Pi # P2 exactly replicates E.
A.7 Proof of theorem 6.3
Proof. Lemma 6.3 follows from Algorithm From Weiss et al. (2021) a RASP program can be compiled to a Transformer, with fixed number of Transformer-layers and attention heads. However, it assumes that the MLPs can perform any element-wise operation. Thus, it suffices to show that each MLP needs O(1)
layers with respect sequence length n.
We first observe that the largest internal value possible within Algorithm 4 is n², there are n² +1 distinct internal values including O. Using 22 log n2] + bits, we represent all of these values unsigned integers. Using floating point numbers we would also need @llogn) bits.
All linear clement-wist operations in Algorithm 4 can be implemented trivially, since an MLP can perform arbitrary linear transformations. Therefore, we focus on the only nonlinear element-wise function [2n
1] [n]
I 1
g(a,b) b) = a, a-
<<b 2 b.
Using a constant number of linear operations and ReLU functions, can be constructed as follows:
g b) = Re - M ReLU(a - e)) + ReLU(a- b),
where 0 < and M 2n
Because g can be implemented using constant number of linear operations and ReLU functions, it can be implemented by an MLP with ReLU activation functions and O(1) depth.
Because of skip-connettions, we can concatenate MLPs by zeroing out attention. Then we can create any MLP of 0(1) depth.
Thus, it possible construct an encoder with L O()) and D O(1) such that ( Im)m fic(II....,Zm) for all sequences of length I
]
Attention patterns of different Transformer architectures
we provide the visualization of attention patterns of encoder-only, decoder-only, prefix decoder- only, and encoder-only models.
In Figure M
C Experiment Details and Additional Results
In all experiments, train encoders in the same manner decoders, processing entire sequences in each batch with single gradient optimization step. Although this approach does not offer the same efficiency benefits for encoders as it does for decoders, we adopt it to maintain consistency between the training processes of both models.
C.1
Count3 with LLM
In the main paper, we fine-tuned two LLMs for Count3: Llama3-8B (ubeyy al. 2024 and GPT-4o (Achiam) al. 2023). Here, provide the details about the fine-tuning of each model. For GPT-4o, we used the official API, setting the batch size to 4 and the learning rale multiplier to 10. For Llama3-8B, we employed LoRA fine-tuning Hu et al. 2022 with a batch size of 16 and a learning rate of 1.4 x 10-4. Regarding
7hhis function implements modular division for bounded range. g(a, mod when S
19

---

Published in Transactions on Machine Learning Research (11/2025)
Prompt: "Encoder only next token prediction"
(Input/Prefix is "Encoder only" in encoder-decoder model and prefix decoder-only model)
Encoder
Decoder
Decoder
Decoder
Encsler Only
Nea
Taken
Enooler
Oal
Nest
Token
Encoder
Only
Neat
Taken
ONl Eneader
UNly Raoder
Okl Excede:
Eacoder
Decoder
Decnder
Not
Nest
Now
Decoder
Tokee
Sakee
Token
Encoder-Decoder
Decoder-Only
Prefix Decoder-Only
Encoder-Only (ENTP)
Figure 8: Attention patterns of different Transformer architectures in next token prediction. Encoder-decoder and prefix decoder-only models first perform full attention on the input (prefix), and then use causal attention to predict subsequent tokens. In contrast, decoder-only models apply causal attention to tokens, without distinguishing between input and output. Encodcr-only models also do not separate input and output, but they recalculate altention from scratch for each token prediction, performing full attention on all tokens.
prompt design, included the algorithm code in the prompt so that the LLMs could leverage its knowledge of natural language (see Table 5). We note that the loss was applied only to the answer part of the prompt.
Additionally, we verify the validity of the prompt design used for LLM fine-tuning. To this end, modify the task from Count3 to Count2 p and fine-tune the Llama3-8B using prompts that include algorithmic code, as in the main experiment. As shown in Figure g the model successfully learns Count2 with the proposed prompt design, achieving high sequence accuracy. This demonstrates that the model's difficulty in learning Count3 due the charactoristics of causal docoder-only architecture, rather than an issue with the training strategy, such the prompt design.
1.0
Llama3-8B Training Loss
Sequence aceuracy
0.8
0.6-
0.4
Llama3 8B Sequence Accuracy
5000
10000
15000
20000
25000
10000
15000
20000
25000
Training step
Training step
Figure 9: Results of LLM finc-tuning on Count2. The Llama3-8B successfully learns Count2 when using the same prompl format as Count3. This demonstrates that the reason LLMs struggle with Count3 is not due to the complexity of the prompt,, but rather the characteristies of the decoder-only model.
C.2 In-context Learning
In this section, we discuss four function classes in the in-context learning experiments (Garg et al. 2022 including the two function classes introduced in the main paper: linear function, sparse linear function, two-layer neural network, and decision tree.
*Count2(1) 22 Bg...,, xn) = fiEniz on = (mod n) (mod n)).
20

---

Published in Transactions on Machine Learning Research (11/2025)
Table 5: Example of prompt used for LLM experiments. We include the code for the algorithm in the prompt to leverage the knowledge of the LLMs.
Prompt:
def f(x: listfint)) -> int:
len(x)
count = 0
for in range(n):
for in range(n):
if [x[i] xfi] + x(-1]) % n 0:
count 1=
return count % n
x = [52, 14, 22, 48, 28, 37, 3, 28, 14, 1, 12, 20, 38, 48, 51, 41]
for range( 48):
(aappen(((x)))
px)
What is the output of this code? ?
Output: [52, 14, 22, 48, 28, 37, 3, 28, 14, 1, 12,
20,
38,
48
51,
41
0,
13,
14,
17,
12,
20,
17,
2,
10,
0,
6, 25
26, 1, 28, 29, 22, 20, 19, 3, 22, 8, 21, 24, 4, 39,
41, 36,
38,
40,
44.
16,
34.
0,
10,
46
5,
51,
8,
32,
15, 44, 54]
For all function classes, the input my is drawn from Gaussian distribution N (0, Ia) where represents the dimension of We provide detailed descriptions of each function class below.
Linear function. We consider the class of lincar functions F = {f f(x) = w x. E Rd) where w is drawn from a Gaussian distribution N La). Following previous work (Garg et al. 2022), we set d = 20 and the number of data points to 40.
Sparse linear function. We also consider sparse linear function, which similar to linear function setup. The difference is that after drawing w from N (0, La), only randomly selected coordinates are kept, while the remaining ones set to zero. Following previous work (Garg et al. 2022). set k =
Two-layer neural network We examine the class of two-layer ReLU neural networks F {fl f(x)= = W W (W())e) W(2) E gixh W()) E [gxd]] where a(-) = max(0,.) (i.e., ReLU function). We set -= 100, d = 20, and the number of data point N to 100.
We consider the class of decision trees represented by full-binary trees of fixed height. Tn these trees, the leaf node values are drawn from N (0, 1), and the non-leaf nodes are sampled from random integers between 0 and d, indicating an index of the input æ. At each non-leaf node, if the value of the input at the specified index is positive, move to the right; otherwise, we move to the left. Given an input, we start at the root node and repeat this process until reaching leaf node. The value of the leaf node becomes the output of the function.
Decision tree
Additional in-context learning experiment results using the four function classes described above are pro- vided in Figure 10 ENTP demonstrates better performance compared the docoder-only models in lincar regression and sparse linear regression, while exhibiting competitive performance in two-layer NN regression and decision tree.
21

---

Published in Transactions on Machine Learning Research (11/2025)
122
1.2
Squared error
1.0
Docoder only
Squared error
1.0
Decoder only
Squared error
Decoder only
Squared error
Deceder only
Encoder-ooly
Encoder-only
Encoder-only
Encoder-only
0.-
0.
24
02
12
In-context examples
In-context examples
In-context examples
In-context examples
(a) Linear Regression
(b) Sparse Linear Regression
(c) Two-layer NN Regression
(d) Decision Tree
Figure 10:
Additional results of in-context learning experiment. The encoder-only models demon-
strate superior compelitive performance across all function classes compared to the decoder-only models.
C.3 Addition
We test the sample complexity of encoder-only and decoder-only Transformers using addition tasks, with up to 3-digit numbers. We sample the dataset of all possible 3-digit addition examples using method similar to the method described in Lee et al. (202)). We start with all 1,000,000 3-digit, 2-digit, and 1-digit addition examples. Then we randomly remove 90% of the 3-digit addition examples, adjusting the ratio of 3-digit to 2-digit examples from around 100:1 to around 10:1. Next we split the data into training, testing, and validation splits, stratified by the number of digits and carries in each addition example. All 1-digit addition examples were put into the training split. Since our models tend over fit the training dataset, we save the model with the lowest loss on a validation dataset. We test decoder-only and encoder-only Transformers plain and reversed addition tasks, using between 1.25k to 20k training examples. All sample complexity tests are run with at least 5 different seeds. We test small models, described in Table 6
Decoder
Test Error Rate
ENTP
10-1
1002
1350
2300
3750
5050
10003
19000 20000
Number of Training Examples
Figure 11: Addition Sample Complexity. The train and test datasets include numbers with up to 3 digits. The dataset uses the plain addition format ($123+456-579$) unlike the results in Figure
We train Transformers to add larger numbers and evaluate their ability perform length generalization. Training is performed on numbers with up to 10 digits, while testing extends to numbers with up to 15 digits. Each model is trained on 100,000 examples using the reversed addition format (Lee el al. 2023 The numbers are sampled to ensure equal probability for each length, without duplicates. Consequently. in larger datasets, there are fewer 1-digit addition examples compared to 10-digit ones, as the total number of possible 1-digit examples is smaller. All length generalization tests are run with different seeds. We test Small-Deep models described in Table
22

---

Published in Transactions on Machine Learning Research (11/2025)
C.4
Model Sizes
In Table 0 main paper.
we provide the configurations of the Translormer architectures used in the experiments from the
Table 6: Model specifications.
Name
Number of Layers
Number of Heads
Embedding Dimension
Small
192
Medium
384
Large
12
12
768
Small-Deep
2
128
C.5
OpenWeb Text
Table summarizes the results on the OpenWebText dataset across two seeds, and Table B lists the hyper- parameters used in these experiments.
Table 7: Minimum values of training and validation loss, as well as perplexity, for decoder-only and encoder- only Transformers on the OpenWebText dataset. Results are shown for each seed.
Model
Train Loss
Validation Loss
Train Perplexity
Validation Perplexity
Decoder-only-1
4.694
4.705
109.3
110.5
Encoder-only-1
4.643
4.650
103.9
104.6
Decoder-ouly-2
4.683
4.696
108.1
109.5
Encoder-only-2
4.628
4.635
102.3
103.0
Table 8: OpenWebText Hyperparameters
Parameter
Value
warmup iters
2000
Ir_ decay___iit iters
600,000
min Ir
0.00006
max
0.0006
betal
0.9
beta2
0.95
weight decay
0.1
block_ size
128
batch size
32
23

---

end if 7: end for end for Published in Transactions on Machine Learning Research (11/2025)
D Implementation of Attention Using O(D) Memory
Algorithm Implementation of Atlention Using O(D) Memory
Require: q Raxd k Ruxdd v R
yn f- 0
2: a < 0
3: b
4: for j = 1 1,...,, n do
5: c - explg kn)
a a+ olyy b+ b
end for
U/ +
10: return Vn
E
Count3 Algorithms
Algorithm Algorithm compute Count3 in O(n²) time and ((1) space
Require: length n sequence of integers (I1,...,,H.) Rn)
1: count f- 0
2: for = -....., n do
for j = 1,..., do
if (x; xy + Fn) (mod n) then
count count
9: return count (mod n)
Algorithm 3 Algorithm to compute Count3 in O(n) time and Onn) space Require: length n sequence of integers (I1,..., Rn)
1: count f-
table t zero-indexed length-n array of 0's
for 1....,m n do
k x, mod table(k] +- table[k] +1
6: end for
7: for i= 1....,n n do
- (z, + zn)) mod
count <- count + table(k]
10: end for
11: return count (mod n)
24

---

Published in Transactions on Machine Learning Research (11/2025)
F RASP Algorithms
In hm and we provide the Python RASP implementation Match3'.
Zhou ct al. 2024 for Count3 and
Algorithm 4 Count3 RASP Encoder Implementation
def g(a, b):
return if else
def count_ tripleteet))))
1dxa indices(x)
set m[i] (x) and last_x(i) x[-1] for all (only possible with encoder) sel_vidth (select (x=x, qax, pred-true))
last_x kqv (k-idxs, qun
vex, pred=equals, reduction="mean")
g(a, b) equivalent = seq_naple (n x, n, 8) # ylil -xli] X.n. seq_nap last_x, g) =[1] (x[i) x[-1]) X
# conut the number of (i, 1) such that y[i] == z[il (A), c kgv(
Ali, j
yli] z[j] else
k-full (x, 1),
q- (x, 1).
(isel_ qty, pred=equala)) * pred=equals, teduction="mean",
sun sum(v) mean v n)
# сonрute count
idxs
# because count <- n22, there exists such that c[i] count X or c[i] -
c[i] handled by default (0) keys
return kqv (k*c, n vec, pred-lanbda a, b: and b, reduction""menn
Algorithm Match3' RASP Decoder Implementation
def (x):
idxs indices
first_x = (k-1dxz, q=full (x, 0),, pred=equals, reduction="nean" causal=True)
# use bitmask to compute nod
127 y -x 128
2 (firat_x + x) 127 z[i] (x[0) x(i)) 128
max max_count [-1]
there exists (1, 1) such that yli] z(j]
max cox_t kqy
k-full
q=full (x, 1),
v=sel (seeec (k=y, qTz, pred-equals)),
pred=equals
Teduction="max".
map (max_count, lambda min(a, 1))
25

---

Published in Transactions on Machine Learning Research (11/2025)
Algorithm 6 Count3 RASP Decoder COT Implementation
def count count_trippett ttri__ttttlttttx (x)
idxs indices (x)
kqv (x=x, q-full (x, EOS), v=idxe, pred=equals, reduction="min', causal=True)
tok_nap lambda a: if a else -2)
kqv (k-idzs. qun 1, v-x, pred-equala, reduction-"meat"
aeq_len = kqv (k=x, q=x, y=idxs, pred=true, reduction="mas causal=True)
seq_les
seq_len
(grik=ixxa, qui, vex, pred=equals, reduction="nax". causal=True)
(k-ixx,, q-j. v-x, pred-equale, reduction="nax", causal-True)
-ix X 1 (last_x xj) 1
y y_mask_urite urite = (n <= idxa) & (idxs < 2 x n)
write (2
idia) (idxs
y_mask_rean read (n < idxs) & (idxs < 2 x n)
z_mask_read (2
idxs) (idxa
n)
z_count = rel_widthl
x=x y_aa
q=z, pred-lambda 8, b: a and o.
causal=True,
count kqv(
s=z_nask_read
g=z_mask_read, v-n + z_maskk_read pred=lambds a, reduction="mean'. causal=frue,
ans = -ount X
ans mask urite idxs - 3 eoe_mask_write
return
y y_mesk_wriss write
+ z_count z_nask grite
ans_mask f_s__ask__riit write
EOS aoa_mask_urite
26


Reviews:
[{"review_id": "mkv0dGFWKY", "reviewer": "Reviewer_LcnL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper challenges the conventional reliance on decoder-only Transformers for next-token prediction and proposes Encoder-only Next Token Prediction (ENTP) as an alternative. The authors offer a comprehensive comparison between encoder-only and decoder-only architectures in terms of expressive power and computational complexity, both theoretically and empirically. A new function, Count3, is introduced to demonstrate settings where ENTP models succeed but decoder-only Transformers provably cannot, and empirical results across several representative tasks—including arithmetic, in-context learning, and language modeling—are presented to support the main claims.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Specifically,\n- The paper offers a careful and detailed theoretical analysis of the expressive power and complexity differences between encoder-only and decoder-only Transformers, supported by explicit theorems (Section 4, Page 4).\n- A central technical novelty is the introduction and empirical investigation of the Count3 task, which is motivated and analyzed in-depth both algorithmically and experimentally (Section 6, Pages 6–9). The discussion is connected to existing complexity arguments, strengthening the theoretical case.\n- Empirical results systematically compare ENTP with alternative architectures across a wide suite of tasks. On the Count3 setup, Figure 3 (Page 9) provides compelling evidence that ENTP learns the task efficiently while decoder-only models (including large LLMs as in Figure 4 on Page 9) fail entirely. Table 2 (Page 10) supports that Match3’, a similar but easier function, is learnable by both, helping calibrate the findings.\n- On small-scale language modeling, arithmetic, and in-context learning benchmarks, Figures 5–7 (Pages 10–11) and Tables 3–4 (Page 12) show that ENTP achieves competitive or superior results on sample complexity, length generalization, and real-word tasks compared to decoder-only Transformers.", "audience_yn": "Yes", "audience_explanation": "As far as I am concerned, researchers in the TMLR community may feel it is intreseting to explore new-architecture of LLMs beyond GPT-style transformer decoders. Though transformer encoder is not a brand-new architecture (e.g., PLMs in BERT-family), I think it is interesting to see the potential of transformer encoder in the next-token prediction language modeling task.", "requested_changes": "- While the existential theorems (Theorem 4.1/4.2, Page 4) and complexity analyses provide insight, the generality relies on idealized settings (unbounded token/embedding dimensions, arbitrary input domains), reducing immediate practical impact. The circumstances where ENTP's theoretical benefits transfer to real world—especially with finite token sets and typical sequence lengths—are only partially discussed (Page 4 and Page 7, top). For instance, the inability of decoders to approximate certain ENTP-expressible functions is shown in a very specific and contrived setting, and does not rule out that for most realistic language modeling objectives, the gap is negligible.\n- The ENTP architecture as presented carries severe computational overhead (Section 5, Table 1, Page 6), scaling as $O(n^3)$ per sequence for time (vs $O(n^2)$ for decoders) and increasing space complexity. While this is acknowledged and framed as a tradeoff, the lack of systematic exploration of this bottleneck in practice limits ENTP's applicability, and no mitigation strategies are attempted. Readers interested in scaling would likely be disappointed by the absence of even preliminary scaling/efficiency experiments or ablations.\n- Most empirical results focus on small or synthetic settings. For actual natural language modeling, Table 3 (Page 12) shows only a slim improvement in validation loss/perplexity, and these are over a relatively small OpenWebText subset with mid-size models. Notably, there are no controlled ablations or extensive benchmarking against strong masked language modeling (MLM) variants or encoder-decoder architectures, nor against recently proposed improvements for next-token prediction efficiency (such as those discussing next-sentence or segment prediction objectives).\n- The impact of ENTP's design on downstream transfer, fine-tuning, compositionality, or large-scale context understanding (beyond length generalization on addition) is only superficially explored. Figures 5–7 and Table 4 hint at outperformance but lack detail on statistical significance, robustness (e.g., random seeds, repeatability), and comparative performance with state-of-the-art models.\n- Would hybrid architectures (e.g., partial causal masks or adaptive masking) bridge the gap between ENTP's expressiveness and decoder efficiency?", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1RbvWcwCtN", "reviewer": "Reviewer_W7Re", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "### Summary\n\nThe paper analyzes how causal, decoder-only Transformers differ from bidirectional, encoder-only Transformers in sequence generation tasks. There are both theoretical and empirical arguments made here.\n\n1. First is **a theoretical result showing that in terms of expressivity, counter-intuitively, neither architecture subsumes the other.** (Note that this result is existential: it constructs a single instance of a function that one can represent, but the other cannot match exactly.)\n   - This is a surprising result since one would typically think that the bidirectional architecture is strictly superior in expressivity.\n   - Note that if one were to consider whether one can at least approximate the other inexactly, then it becomes clear that the bidirectional model can approximate any decoder model, after all.\n   - The result admittedly holds under some specific limitations/assumptions.\n\n2. The next main result is **the theoretical analysis of an autoregressive sequence-generation task** called Count3 (which is repurposed from an existing task in literature).\n   - Here, it is shown that a causal transformer would require layers growing with the sequence length whereas a bidirectional one can do with constant number of layers.\n   - Note that the theorem holds under an assumed conjecture (a reasonable one).\n\n3. Finally, **two sets of empirical results** demonstrating the superior performance of the encoder-only architecture:\n    - First, are on the Count3 task demonstrating a gap in performance on some decoder-only, prefix-based decoder-only, and some medium-sized and large BERT-based encoder models.\n    - Other empirical results on addition (length-generalization, sample complexity), in-context learning, natural language tasks (commonsense reasoning, classification)\n\n\n## Strengths\n\n1. The paper analyzes a good scientific question. Even though\n    - bidirectional attention is expensive and currently impractical, and\n    - it may be unsurprising that it must have some superior expressivity or capabilities or sample complexity, \n\nthis gap must be quantified and studied scientifically. We need to know what the headroom is, and have insight into when/what type of task this becomes relevant. The paper addresses this.\n\n2.  The analysis is clean and understandable. The examples studied are easy to follow and illustrative. There is no unnecessary mathematical obfuscation. I found this a pleasure to read.\n\n3. The paper encompasses both theoretical and empirical analyses, and these analyses complement each other well. I contrast this against a paper that is focused on proving theorems, or a paper that is a collection of empirical results.\n\n4. Importantly, the paper is honest about its limitations where applicable. \n\n\n## Weaknesses\n\nThere is an obligatory list of weaknesses I could state:\n- I would say that the overall claim is qualitatively expected. \n- Furthermore, the theoretical constructs (e.g., the Count3 task) may appear a bit artificial. \n\nBut I would state these as acceptable weaknesses for the chosen direction, and for the style of accessible result the paper aims for.\n\nHowever, I require some major clarifications before acceptance.\n\n\n## Major Clarification question 1\n\n**Do the experiments in Sec 6 report a gap in training accuracy or test accuracy? (e.g., Fig 3 right?)**  (There’s a similar clarity issue in Fig 7) **This is an important question because it somewhat contradicts my expectation.** Let me explain.\n\n\nThe theorem in Sec 6 presents an expressivity gap in a task (not in the ability to learn with gradient descent). It’s possible that when it comes to _learning_, both architectures fail (thus, the gap goes away). Now, it’s clear that the experiments demonstrate a gap in training loss (this is still an expressivity gap). But is it also demonstrating a test accuracy gap? \n\nThis bothers me because I would find it surprising if this task can be learned in the first place with any architecture, without any step-wise supervision or some form of curriculum (i.e., train on a mixture of Count3 with n=1, 2, 3…). The task involves composing multiple subroutines, which is generally a hard learning problem. See for example Fig 2 in [1] who use a mixture of various task complexities.\n\n\n## Major Clarification question 2\n\n**The claim at the end of Sec 4 doesn't seem justified:**  At the end of Sec 4, the paper promises that the converse approximation result does not hold. I.e., “there exist some ENTP models that decoder-only\nTransformers cannot approximate.” But the theorems still talk about exactly fitting the counts. Could you clarify? Perhaps this claim needs editing.\n\n\n## Minor clarification question 3\n\n**A jump between the empirical and theoretical claims:** The theoretical results are about expressivity; but some of the later empirical results involve sample complexity (which relates to learning). There seems to be a jump here that the paper is a bit casual about, and does not make the reader aware of. I would like to hear more from the authors about this: is there intuition for the sample complexity gap?\n\n[1]: \"Transformers, parallel computation, and logarithmic depth\", Clayton Sanford, Daniel Hsu, and Matus Telgarsky https://arxiv.org/pdf/2402.09268", "claims_and_evidence_yn": "Yes", "claims_explanation": "I checked the main paper's proofs which look correct. There are also empirical results which corroborate the claims.", "audience_yn": "Yes", "audience_explanation": "The paper presents an accessible set of quantitative and analytical results demonstrating the effect of a fundamental aspect of language models (the directionality of the attention mechanism). The results are both theoretical and empirical in nature, and would thus be of  significant interest to a broad range of readers in the TMLR community.", "requested_changes": "Please provide clarifications to my questions, and update the paper accordingly. Importantly, it is unclear what exactly the experiments on Count3 demonstrates -- this would help me assess the relevance of these experiments to the main claim.", "broader_impact_concerns": "Not applicable.", "additional_comments": "Some suggestions:\n\n1. Given that Theorem 4.2 is a bit counterintuitive (it says that ENTP does not strictly subsume causal decoder-only models), the reader would benefit from proof intuition here. \n2. The introduction of the task in Eq 6 should immediately let the reader know that the task requires the model generating multiple tokens or equivalently that the equality should hold for various values of m ranging upto some length n.  My initial impression was that we only need one equality to hold at position n and so the proof confused me a bit.\n3. Under 6.1, the text reads “sequences generated from Equation (6)” I’d add “under a distribution defined as follows”, because Eq 6 does not fully describe a generative process. \n4. In Conjecture 6.i, it wasn’t immediately clear what “with access to x_n” meant until I read the proof.\n5. In Section 7, I’d reassure the reader that the two models you compare are of similar sizes. (I had to chase the links down to verify what models were used.)", "extra_scores": {}, "extra_text": {}}, {"review_id": "4XWPXHvBTx", "reviewer": "Reviewer_6n5B", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors studied an encoder based next token prediction transformer, where Figure 1 provides a clear picture of the architecture and method. The authors demonstrated that encoder and decoder architectures have distinct representation powers theoretically, but more importantly identified a task - count3 - that only encoder based transformers seem to be able to perform. There is also additional theoretical results on the complexity of such tasks as well, along with further experimental results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "All theoretical results came with associated proofs, and all of them after a high level read appear sound, albeit I did not check super carefully about potential mistakes. \n\nConjecture 6.1, while not proven, seems highly plausible given the authors provided Algorithm 2 and 3, which does indeed appear optimal. It also appears potentially challenging and somewhat outside the scope of this paper to prove the conjecture, so it is appropriate the authors left it as unproven. \n\nFigure 3 and 4 provides very convincing empirical evidence that count3 is a solvable (albeit not necessarily trivial) task for the encoder based architecture, while simultaneously showing that the decoder based architecture cannot solve the task easily (note the saturation in Figure 3 left at step 10k-12k for decoder architectures).", "audience_yn": "Yes", "audience_explanation": "While the encoder based architecture is less efficient computationally, it remains interesting to study the behaviour as a theoretical tool to understand the complexity of certain language type tasks like count3, as well as the limitations of decoder only architectures. For one, it is surprising that not only decoder based architectures fail at count3 but also encoder succeeds. This itself is a sufficiently interesting read for me, and I believe it should be interesting to many other audience members of TMLR.", "requested_changes": "Most of the paper is well written, except I would like a clearer mathematical description of the difference between decoder-only and encoder-only next token prediction. Figure 1 is quite clear, but the structure is not very obvious in the mathematical setup. Perhaps the authors can consider writing down literally the equations corresponding to Figure 1 and highlighting the difference.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)