DeltaFormer: Unlock the state space of Transformer
Authors: Mingyu Xu
Tenglong Ao
Jiaao He
Jianqiao Lu
Guang Shi
Shu Zhong
Venue: NeurIPS 2025 poster ()
Keywords: Transformer
Circuit Complexity
Model Architecture
Primary area: deep_learning
TL;DR: We propose a more expressive Transformer, which exceeding its original $TC^0$ expressiveness.

Abstract: In recent years, large language models with Transformer architecture as the core have made breakthrough progress in many fields. At the same time, there are also some weaknesses in the large language model that have prompted people to reflect, among which the most fundamental one is the reflection on the Transformer architecture. The Transformer architecture has high parallelism and can fully utilize the computing power of GPUs, thus replacing models such as LSTM in the past few years. However, high parallelism is not a free lunch, as it fundamentally limits the performance of models. Especially, the problems that logarithmic precision Transformer architecture can solve are strictly limited to the $TC^0$. And there are many important issues that are usually considered out of $TC^0$, such as Python code evaluation, entity tracking, chess, and other state tracking tasks. Meanwhile, some recent state space methods based on Delta Rule have been able to break through the $TC^0$ architecture, but they are limited by fixed size state spaces and perform poorly on many tasks. To this end, we have re-examined the Transformer from the perspective of a state space with kernel functions and propose an improved Transformer called DeltaFormer. We have theoretically and practically demonstrated that the proposed new architecture can break through the limitation of the inherent $TC^0$ expressivity of Transformers and verified that it is not weaker than standard Transformer in language modeling tasks. We hope our work can provide inspiration for designing more expressive models.

Former: Unlock the State Space of Transformer
Mingyu Xu' Seed Team, ByteDance xumingyu@bytedance. com
Tenglong Ao Seed Team, ByteDance
Jiaao He Seed Team, ByteDance
aotenglooggbyytedance.c com
hej seejiaao@bteedacce.coom
Jianqiao Lu
Guang Shi Seed Team, ByteDance
Shu Zhong Seed Team, ByteDance
Seed Team, ByteDance luj lujiaaggaa@byytedacc.....
shiguangebytedance.. com
zhongshu@bytedance.co
Abstract
In recent years, large language models built around the Transformer architecture have achieved breakthrough progress many fields. At the same time, certain weaknesses in these models have prompted further reflection, with the most funda- mental concerns centered on the Transformer architecture itself. The Transformer offers high parallelism and can fully exploit the computing power of GPUs, which has enabled it to replace models such as LSTM over the past few years. However, high parallelism is not free advantage, it imposes fundamental limits model performance. In particular, the problems that the catrrithmi--precisiii Trans- former architecture important tasks are generally considered outside TC", including Python code execution, entity tracking, chess, and other state-tracking problems. Meanwhile, recent state-space methods based on the Delta Rule have been able to surpass the TC" limitations of the Transformer, but these approaches suffer from fixed-size state spaces and perform poorly on many tasks. To address this, we re-examine the Transformer from the perspective of a state space with kernel functions, and propose an improved architecture called DeltaFormer. We theoretically and em- pirically demonstrate that this new architecture can overcome the inherent TC* expressivity limitations of standard Transformers, while remaining at least as effec- tive in language modeling tasks. We hope our work will inspire the design of more expressive models.
solve strictly bounded within the class TC². Many
Introduction
In the field of artificial intelligence, the Transformer model 771 has attracted widespread attention for its outstanding performance and broad application prospects since its inception. As the core architecture of modern AI systems, the Transformer has demonstrated remarkable results in various domains [9] 32
19 55 [6]. Despite its significant success, the Transformer has shown poor perfor- mance many tasks that lack chain-of-though reasoning, which has prompted reflection among researchers.
Another noteworthy observation is that existing large models have demonstrated impressive reasoning abilities following reinforcement learning 30 64) However, recent studies indicate that RL does not unlock fundamentally new capabilities, and that their abilities remain constrained by the pre-training phase [79 65). Since model architecture lies at the core of pre-training, researchers have increasingly turned their attention to its iniitations-paaticalle the expressivity of Transformer
"Equal contribution.
I Corresponding authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

models. Existing Transformer- models possess restricted expressive power, it has been shown that they belong to the TC. complexity class
44 Solving problems larger classes requires the use of shain-of-thoughe reasoning 244 37.. Moreover, numerous real-world tasks go beyond TC and fall within NC such as entity tracking, Python code evaluation, and chess state tracking [42]. This limitation may be a fundamental reason why current large-scale models exhibit randomness in entity tracking tasks [13]. This naturally raises the question: is it possible to break through the TC
expressivity barrier that constrains the Transformer?
In the domain of finite state-space methods, recent work has shown that the delta rule can be used to surpass the expressivity limits of TC [52 66]. However, these methods rely on finite-sized state spaces, which inherently face challenges, such as difficulties in performing retrieval tasks [31]. A natural question follows: can we draw inspiration from these approaches to design a more expressive Transformer?
To address this, we re-examine the Transformer architecture through the lens of kernel functions and the delta rule, proposing a new model called DeltaFormer. We theoretically and empirically validate that DeltaFormer possesses expressive power exceeding that of standard Transformers, while maintaining comparable performance in language modeling tasks.
The main contributions of this work
follows:
We revisit the delta rule from the perspective of kernel functions and propose new architec- ture, DeltaFormer, which implicitly assigns a state space to the Transformer. In addition, we design chunk-wise algorithm that enables DeltaFormer to be efficiently implemented in parallel on GPUs.
We theoretically demonstrate that DeltaFormer has stronger expressivity than the standard Transformer. We prove that by combining the delta rule with non-linear kernel, KV cache of size O(T' log n) can track 7 exchanges among n objects. Furthermore, if the KV cache is compressed every O(n) steps, only (n log n) space is required, which is significantly smaller than that needed when using linear kernel.
2 Related Work
Circuit Complexity Boolean circuits have long been used to study parallel complexity. Among the most important complexity classes in this context NC and TC. The TC class focuses on problems solvable by Boolean circuits in which majority gates are the primary operation, while TC specifically denotes problems solvable by constant-depth, polynomial-sizz threshold circuits. For an input of length n. previous work has shown that constant-depth Transformers with finite-precision (size poly(n)) embeddings can only solve problems in TC without chain-of-thoue thouhhtttt reasoning Recently, several studies have demonstrated that DeltaNet [63
77) and related variants [76 52 66
can overcome the TC complexity limitation inherent Transformers. These architectures exhibit
higher expressivity and achieve improved performance in tasks such state tracking [27 66 42
Model Architecture Over the past years, researchers have explored various architectures to en- hance model capabilities, ranging from early RNNs [46] and LSTMs [69] to today's 's dominant Transformer (1].. Transformers have quadratic complexity, and numerous efforts have sought to
5 54] Nevertheless, Transformers still possess many valuable properties that are not easily replaced, particularly their ability to perform information retrieval and
improve their efficiency [51] 28
68
adapt forms of dynamic sparsity K 47). Currently, many popular language models [ 20 75
continue to use Transformers as the core architecture, while some employ hybrid designs (58 38 35
Our work aims improve the Transformer by breaking through its expressivity limitations. We summarize the relationship between commonly used model architectures and their parallelism in Figure
Understanding Transformer Since the rise in popularity of the Transformer 771, extensive research has focused on understanding its underlying mechanisms. Several works analyze its 34] while others explore the dynamics of model
powerful approximation capabilities [80] 18
training [1 7 70 and interpretability 10
2] With the advent of large-scale models, increasing attention has been devoted to studying the contextual learning ability of Transformers [25]
39 40

---

Expressivity
Lineur Prugramming
RNN
Matrix Inperse
Acyolic BCQ
STCON CST
FoizoFormar,
S Partey
Deitaliet et
Trans Transformer.
Unary Language
Lineur Trunsf
Parallefism
NC² LOGCFL
NC1
TC²
ACe
Figure 1: Parallelism and expressivity between models. The higher the parallelism of a model, the more restricted it can be. Previous work has shown that the Log- Pre-Prcciioon Transformer is in TC [4]] and constant precision Transformer in AC [37]. The model based on DeltaNet can perform tasks that exceed the expressivity of TCC", if we accept that TCC" o NC [52]. In addition, even for models with the same degree of parallelism, their performance is affected by the model capacity. One of the most intuitive examples is that Transformer can perform better than Linear Transformer in retrieval related tasks [I].
36 49
73 An important aspect in understanding the behavior of large models is their 4%
33 72.. The delta rule can also be interpreted as an update mechanism for associative memory. In this work, we re-examine the delta rule from the perspective of kernel functions and propose new model based on this insight.
associative memory
Method
3.1
Re-examining the Delta Rule from the Perspective of Kernel Functions
The delta rule has a long research history 67
and has recently attracted renewed interest among researchers studying model architectures 663 77 52 Its name comes from updating weights based on the difference between the prediction and the target. Mathematically, let the state space at time f be denoted by S., the input by k, and the target by 74. The model seeks to minimize the Euclidean norm S| Us 12. Applying one step of stochastic gradient descent (SGD) with learning rate Bg yields:
S441 St 3, v.)kk
(I)
= = (I B.kak( B.ack]
(2)
To retrieve information from S,, we use:
0, S44s-
We now generalize this process by introducing a kernel function x(x, TTa))T(y))) where y, pd and (--) is mapping to (possibly) infinie-dimensional space. The delta rule with kernel function becomes:
S S, (I ((o(()))) + (eer
(4)
and information retrieval is performed via:
o: = S.v(gg).
(5)
However, this formulation poses two significant challenges. First, both the kernel function v6(-) and the state matrix S, are infinitediimensionall making them infeasible for explicit computation on conventional hardware. Second, updating S, at each timestep is computationally inefficient; this inefficiency is one of the key reasons why traditional L.STMs have lost popularity in recent years. Therefore, is essential to develop efficient GPU-friendly implementation.

---

3.2 Rewriting the Expression for Practical Computation
We can rewrite Eq. 4 a simplified, equivalent form: St+1 Si+ Bouck, where ur = 2t (k))(k)) determined by (K2, u,) Using the derivation Appendix [A
we obtain:
t-1
U = Beul - Be
kaks, ki)) us
(6)
=
Σ ==1
k(ki, q:) u4.
Although (-()) may map to
space, (b-) does not explicitly appear in Eq and Eq. 7 and all terms in these equations can be computed finite form. If we set s(x, y) = x this formulation exactly corresponds to DeltaNet 663 77). Details efficient GPU implementation provided in Section 3.4
Generalized Design. (K1, K2) in 6 and Eq. using different gating parameters (a,, S.) to scale e, and Σ k(k;, ke ),, and introducing Wt in Eq. to control write and delete operations instead using k; directly. This yields:
We can generalize the above formulation by applying separate kernel functions
Ut = 044 - Be Σ Ki (ks, wi) ue
(8)
0t
Ko (Nis; gr) ug.
1=1
Eis exp
Re v3
m
we set Br = 0, ar = 1, and define: O2
the formulation degenerates to the
Σ
exp
standard Transformer. We refer to Eq. g and Eq, collectively as DeltaFormer. In the following, we compare the advantages of DeltaFormer over previous models such as the Transformer and DeltaNet.
3.3 Beyond the Expressivity of Transformer
As previous literature have shown, the performance of Transformer limited to TC if chain of thought is not performed 44 37 24). Based on hypothesis that is considered correct, TC" + NC1, We will prove that DeltaFormer can solve problem which is NC commleeee under AC reduction. This task is to track the exchange of (n 2 5) elements (78). Specifically, we provide constructive proof as shown in Theorem and the detailed proof is in Appendix
Assumption There exist state points d-dimensional unit sphere, and the absolute value of the inner product of any two distinct state points is less than or equal to c(d, n), which means:
3 31 .2,....,,, In E IRd S.t. | 1(7)),
max |o 23 S c(d, n) igs
Assumption There is a f.function f satisfies:
Yx E (-1,0,1,2), Vi E U(z 4c(d, f(0)=
Theorem Based the above assumptions, {(k1, vi)...., (Kn, v. The keys {ki,..., )n lie on a d-dimensional unit sphere and satisfies Assumption 1, which means:
consider initializing n. key-value pairs
Vi,j E (1,..., n), # | 1,
[1 kyl <(n, d).
and define an attention mechanism as follows:
[(k kz) Or = Σ fla ks)w:
u, = v1

---

where f()) satisfies Assumption and it is noted that v E {l...... n., since f(k k2) = O, we have u, Ve.
Ar the current step t, 1. > n, the value corresponding to kg is denoted by 0g E {1, (1,..., ......,1), n). Note that, after 1 exchanges, is not necessarily equal the initially assigned Us. V1 S l2 4 S to exchange the stored values Ut, and Ut, corresponding to kt, and kzz, it suffices to construct:
k2 ke. -Kez 2
When reirieving the values:
Query q: = kt., then Og = -'tzi
Query q: = ktz, then iiz1
Query q: ktg. ts n, to F t1, 12, then Os Big-
This implies the exchange of values corresponding to kit, and Kitz is completed.
3.3.1 Re-examining the Assumptions
We now revisit the two assumptions in Theorem 1
What relationship between d and n must hold for Assumption to be satisfied? According to Theorem 5.2.1 in [8), For every a E (0, 1) and E > O, there exists e > 0 such that for every d, one can fin at least 2dd unit vectors in Rd whose pairwise inner products all lie in [a- a + c]. Setting 0.01 and 0.1, we obtain e(d, n) 0.11 < } This implies that for Assumption to hold, is required that: (llogn)) n).
Regarding the choice of f()) in Assumption 2, one straightforward option is to use the rounding function r-)nd(.). i.e., mapping the input to its nearest integer. With appropriate rounding precision, this function can satisfy the assumption. If we instead adopt the commonly used exponential kernel exp(.), theoretical results show that a multi-query attention mechanism with four shared heads can express function (()) that fulfills Assumption 2.
In summary, according Theorem [ delta rule-based no-linear kernel attention can achieve state exchange between historical timesteps t and 12, with d = O(log n).
Space Cost Analysis In Theorem 1 suppose we wish to track T exchanges among states. Clearly, we must set d Ologgn) n) and maintain a KU cache of length T. This results in a space cost of: O(Tlog
If we read out (01, (U,,..., ) based on kk!....,kkl every ((n) steps, and then rewrite {(k,, i into the KU cache, we only require KU cache of length On)) This reduces the total space cost to: (n log n), which is significantly smaller than the O(n?) space required when f(.) is an identity mapping. For example, RWKV7 [52] uses 5 x 5 matrix to track the exchange of 5 elements. To provide clearer comparison between linear and nonlinear kernels, we have restated both versions of Theorem in Appendix
For comparison, employing non-linear kernels unlocks the full potential of the delta rule: we can track the exchange of exponentially many states, rather than just the n = O(d) most recent states.
In summary, DeltaFormer-as generalized form of the Transformer- not only surpasses the inherent TC expressivity limitations of the original Transformer, but also tracks the exchange of n objects using significantly smaller state space than models such as RWKV7.
3.4 Efficient Chunk-wise Algorithm on GPUs
High parallelism on GPUs has been a key reason why Transformers have outperformed non- parallelizable models such as LSTMs during the scaling era of large models. From high-level perspective, however, there exists fundamental tension between parallelism and expressivity. No- tably, the parallelizability of DeltaNet is lower than that of a standard Transformer; if reduced to the level of an I.ST,, would lose much of its practical appeal. Therefore, in order to make a more expressive model practically useful, must devise implementation that runs efficiently on GPUs.
5

---

Consider q, k, v, E R", sequence length T, and assume T > d. For simplicity, and without loss of generality, we focus efficiently computing:
> k kz) 14, where the computation
of or follows similarly to FlashAttention [I5]
If we compute {ui...., ur} directly according to the above recurrence, the computational com- plexity is dl) Since each un depends all previous Uict, this algorithm is inherently sequen- tial reluirnng (T") iterations- and thus cannot exploit GPU parallelism.
Matrix Formulation.
We can express the recurrence in matrix form as:
U = V AU,
(10)
where the 1-th rows of U and V are given by Uz.: We and Ve, t. respectively. The similarity exp(k; kt) for a normalized exponential kernel, or %,
matrix A is defined by: A,,; hi), e.g.,
kg ky for linear kernel. Since A is lower triangular, U be solved via:
U= (T -
(11)
This formulation requires matrix inversion, still costing O(Tad) operations, but crucially it is fully parallelizable on GPUs.
Chunk-wise Parallclization. A compromise between the two approaches above can be achieved via chunk-wise processing. Divide the sequence of length into N equal-sized chunks, each of length C [T/N], Then, compute within each chunk using parallelizable matrix operations, processing the chunks sequentially.
This reduces the number of recurrent steps from O(T) to O(N), while computational complex- ity changes from O( to: O(T2d TCd TC*). In essence, this method trades additional computation for reduced runtime For pseudo-code of the chunk-wise implementation, refer to Appendix
Experiment
4.1 Track the Exchange of Elements
5
Swap [1, 2]
Swap [2, 4]
Figure 2: Swap task diagram. At the beginning, tokens of different colors placed positions 1 to 5, and the tokens of two positions are exchanged at each step. We expect the model to query what the token for each position is each step. Simply but without loss of generality, we default to outputting the token at the first position to avoid introducing a "query token". This task can also be tokenized into task with input vocabulary size of Cg 10 and output vocabulary size of 5.
Although Theorem establishes that DeltaFormer can theoretically track the exchange of n objects, remains necessary to validate this capability empirically. Specifically, we investigate whether DeltaFormer learn track the exchange of objects from data when trained using gradient descent. To this end, we design an experiment to verify this property. The experimental setup is illustrated in Figure with default context length of 16.
DeltaFormer can track the exchange of elements. We compared DeltaFormer and the standard Transformer under various designs of the similarity function, as shown in Figure 3 Across almost all reasonably simple choices of xi (-), DeltaFormer achieved better results than the Transformer. In
'Our code is available at /tttps//githai com htt.//lloor//fsaaaaaaaaaaa linear attentionn/llob/aai.. fla Lla/layerrs/celaatommss .y and in the supplementary materials.

---

(a) Transformer.
(b) DeltaFormer.
(#1 (2, 2)
DeltaFormer. (K1
I
#
I
y
(d) DeltaFormer. (#1 max( 0,0))
(c) DeltaFormer. (R1
(1) DeltaFormer. (Kas (2, v) softmar((z y))
exp(x" y))
Figure 3: Comparison of Transformer and DeltaFormer using different similarity functions K²(+) for performing swapping tasks. For rg(-)), we use the softmax function to maintain consistency with Transformer. Pay attention the scale of the y-axis. To ensure convergence, [-] means round two decimal, such as [1.236] = 1.24.
particular, a 1-layer DeltaFormer was able to execute and track the exchange operations elements. In contrast, increasing the number of Transformer layers did not yield improvements.
The similarity function used Eq. Bis important tracking. Another key observation that the choice of similarity function has significant impact on exchange-tracking performance. As shown in our constructive proof in Theorem I the appropriately chosen similarity function can track 5 elements with perfect accuracy. The closer the chosen similarity function is the constructive form, the better the tracking performance. The normalization term in sof tmax negatively impacts the similarity computation when using the exponential function exp(.). Notably, in our experiments the retrieval similarity function K2 (used in Eq. 9 was not based on the constructive similarity so as remain consistent with standard attention but instead used sof tmax. Even in this case, suitable choice of i can still achieve 100% tracking accuracy. Theorem Sacoremmeefecoee Jeffectively proves that is possible retrieve element values each position via specific form of u, meaning that the exchange of elements is implicitly captured in the update of u.
Intuitively, an inappropriate choice of leads to greater cumulative error in updating u. From a mathematical standpoint, this corresponds to the perturbation an inverse matrix that may be ill-conditioned. For details, see Appendix F We also performed stress tests using the Round and Linear kernels in Appendix B.I tracking exchanges of
128 elements.
The similarity function used in Eq. important for retrieval. In the generalized DeltaFormer formulation, the similarity function K2 directly affects retrieval ability. We conducted experiments on the MQAR benchmark [4], with the following configuration: vocab_stt __iiseee_e 256. input__eee seart_sse_lle_ len 128. num_kv lvr_aiirss---a 32, and d_model = 32. To isolate retrieval ability, we used linear kernel so not to enhance performance via similarity scaling. The results show that retrieval performance with purely linear kernel is poor.
Linear
Round
ReLU
Softmax
Accuracy (%)
85.6
91.6
99.5
99.1
Table Impact of K2 on Retrieval Performance
Curriculum learning important. As shown Figure training directly with a context length of 256 led to very slow convergence. We therefore adopted curriculum learning, starting with length 32 and gradually increasing the window size, i.e., gradually raising task difficulty. Under such schedule, the model achieved better performance with less computation.
We

---

(a) DeltaFormer with RoPE.
(b) DeltaFormer with NoPE.
Figure 4: Comparison of DeltaFormer using different learning strategy and position embedding.
Each use K₁ (z, y) = 1x" yl- "32 to 256" means that the initial training length is 32, which means the number of swaps is 32. When the accuracy reaches 0.99, the training length will be doubled until it reaches 256. And "256" means that the model is trained on training length of 256 from the beginning. The y-axis reflects the accuracy at the current training length.
The role of rotary embeddings. Since Theorem 1 does not require positional embeddings, conducted experiments removing the default rotary position embeddings (RoPE). Without RoPE, convergence slowed and training directly length 256 yielded random scores. However, under the "32-+256" curriculum, accuracy reached 100%. Moreover, NoPE models degraded less at jump points during length extension, suggesting better generalization. We speculate that while RoPE may hinder expressivity and extrapolation, can facilitate optimization.
Reachability of directed acyelic graphs
Furthermore, design a simple graph connectivity task to evaluate reachability in a directed acyclic graph (DAG). For simplicity, we consider only whether the first mode-given specific topological ordering can reach other nodes. Initially, each node encodes only its immediate neighbors. Since the final output is binary (True False), we avoid class imbalance by dividing the nodes evenly into two classes and constructing tree for each class. We then examine reachability from designated root node, encoding for each node only the information of its parent.
Transformer.
(b) DeltaFormer.
Figure 5: Comparison of Transformer and DeltaFormer using different similarity functions Ki (-).) for performing swapping tasks. For K2(-),, we use the softmax function to maintain consistency with Transformer. Pay attention to the scale of the y-axis.
DeltaFormer outperforms Transformer. We conducted experiments on 32 nodes, as shown in Figure 5 A multi-layer Transformer struggled reach 100% accuracy, whereas single-layer DeltaFormer performed highly accurately. In theory, a Transformer requires Ollog n) layers to perform connectivity checks on n nodes [6]]. However, based on Figure [5a we speculate that optimization challenges also limit the Transformer's effectiveness in this task.
The power of matrix inversion. As shown in Eq. the computation of can be rewritten using matrix inversion. If the adjacency matrix is known, connectivity between nodes and j can be checked by computing A? ..... A" and examining whether the (i,j) entry is positive. Since AI- approximates I A+A+.... AA" matrix inversion substantially enhances model expressivity, particularly for graph-related tasks.
Relation to chain-of-thought (CoT). The limited depth of Transformers has motivated approaches such CoT [74] 37 and the Universal Transformer [6 26), which loop through the layers. In

---

contrast, our method effectively increases depth along the sequence dimension. This yields higher token efficiency for tasks like DAG connectivity: for constant-depth Transformer, directed graph reachability requires (n²) CoT steps [4], reduced to O(n) with continuous CoT 83]. while DeltaFormer achieves the same in single forward pass.
4.3 Language modeling
To verify that DeltaFormer does not affect language modeling capabilities, we conducted experiments on small scale. Following prior work (76),
open-source code of them and open-source dataset Fineweb-edu for training and the open-source evaluation tool Im-evaluation evaluaaiionhharess -arnness for benchmark evaluation. The benchmarks that include LAMBADA [LMB.:[[0]], PiQA HellaSwag [ellla[[8]]] WinoGrande [Wino.; [60]], ARC-easy (ARC-e) and ARC-challenge [12) Boolq [1I, OpenbookQA [OBQA.; 45 SIQA 662 and Copa [57]. We train 340M parameter scale
with 15B tokens with peak learning rate of 2e-3. The context length is 2,048 and the global batch
size is 0.5M tokens. The experimental results shown in Table
Model (5KMM)
ARC-c
ARC-2
Roolq
Copa
Hella.
LMR.
OBQA
PIQA
SCIQ.
Wino.
acc
Irateformner DeltFooreer
28.38
39.61
00.00
68.00
40.11
34.50
38,40
67.25
81.60
52.01
Ni (R.
29.01
59.09
00.52
69.00
40.43
34.17
38.20
67.90
80.60
50.04
N1 Retula
68.00
51.22
81 x)
[a s]
28.50
58.13
60.09
70.00
40.29
33.03
35.40
67.03
81,50
51.92
N1(2.)) softman(e
28.92
69.00
4021
67.21
52.41
Table 2: Comparison of DeltaFormer and its variants various language modeling benchmarks the model with 340M parameter.
Due to the fact that at this scale, the fluctuations of one two points in these benchmark indicators are considered random. Therefore, we can say DeltaFormer is not weaker than standard Transformers in language modeling tasks. Even with different similarity functions, the differences are very small, which is also different from the findings of Section 4.1
Later, conducted experiments the 14B activated MOE model, where the number of key and value was 1/4 of the number of query. As a result, the flops in the self-attention section increased by 25% %, and in the entire MOE model, the flops increased by 3%. The results listed in Table 3 and Table 4
COPA
ARC-E
ARC-C
PIQA
C-Eval
MMLU
RACE-High
RACE-Middle
SIQA
Winogrande
Average
Transformer
50.8
55.6
Deltafoomer
74.6
82.9
51.2
79.4
46.3
45.2
49.0
62.9
54.7
67.2
61.34
+1.4
-0.9
Table 3: Benchmark Comparison. We compared the transformer model and delta model with 14B total parameters, and they trained 500 tokens each.
General Domain
Code Domain
Training tokens
Transformer
DeltaFormer
Transformer
DeltaFormer
100
2.06256
2.06254
1.52628
1.48656
200 B
1.94337
1.94336
1.42112
1.37757
300
1.88013
1.87554
1.35612
1.32587
1.83119
1.83558
1.32285
1.29567
500
1.81472
1.81032
1.31231
1.28326
Table 4: Benchmark Comparison. We compared the transformer model and delta model with 14B total parameters, and they trained 500 tokens each.
Firstly, the benchmark results show that the DeltaFormer outperforms the baseline. Then there is the result of training loss, which leads by 0.003 on the general domain, basically aligning with the slight increase of 3% flops. However, on the code domain, the loss leads by 0.05. When training 300b. The training token can match the baseline training of 400b, which far exceeds the gain of flops. We believe this is due to the higher expressiveness of DeltaFormer, as the code data includes Dyck grammars that match left and right parentheses.

---

Discussion
Expressivity. Since matrix inversion lies within the NC complexity class [4]. the theoretical upper bound of DeltaFormer is likewise in NC2. We can design models with higher expressive power the cost of reduced parallelism, in the extreme approaching inherently sequential models such as LSTM. Ultimately, a trade-off between parallelism and expressivity must be struck, influenced by hardware and environmental constraints. On this trade-off curve, scaling a model with slightly lower parallelism but higher expressivity than the Transformer may serve as a starting point. Identifying models that fully exploit NC may be a promising direction, as many practical models fall within this class, which still allows for parallel exccution.
Optimization, Achieving a strong model also depends on optimization. We observed phenomena such as curriculum learning-graduall extending context tracking tasks. Differences between DeltaFormer and standard Transformers likely lead to distinct optimization behaviors. Furthermore, discussed in Section 4.1 rotary position embeddings (RoPE) appear to hinder performance but aid optimization. A deeper study of the optimization dynamics of such models is interesting avenue for future work.
DeltaFormer in element-
Scaling. Scaling DeltaFormer to larger models and examining the effects will be valuable. We speculate that Transformers require deeper architectures to handle tasks beyond their expressivity, whereas DeltaFormer may achieve such tasks with fewer layers, leading to different optimal depth- to-width ratios. To optimally configure DeltaFormer, original Transformer components may need rethinking. Exploring parameter scaling analogous to Transformer scaling laws is also of interest.
Limitations
First, although we propose an algorithm that executes efficiently on GPUs, current performance is not optimal and further improvements are needed. Second, our evaluation focuses on toy tasks and small-scale language modeling, without large-scale industrial training confirm gains for complex tasks. Additionally, naive layer mixing of linear DeltaNet and standard Transformer could yield hybrid model with both trak-ina and long-text retrieval abilities. Such hybrid may have reduced state-tracking capacity but might still suffice for real-world applications. Comparisons between DeltaFormer and simple hybrids thus require validation on practical tasks.
Conclusion
We extended the delta rule with kernel functions and introduced DeltaFormer. We proved, both theoretically and empirically, that DeltaFormer surpasses the TC expressivity limit of Transform- In particular, introducing nonlinear kernels enables DeltaFormer to track exponentially many element exchanges within the same dimension compared to linear kernels. Experiments indicate that DeltaFormer matches the standard Transformer in language modeling performance. In future work, we aim to scale Felmerormer to industrial-Ievel training, and hope our findings inspire new Transformer designs with improved expressivity.
10

---

References
[1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidr, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint 1rXi:23303.08774,, 2023.
[2] Zeyuan Mww.e--Zuuuuu ICML 2024 Tutorial: Physics of Language Models, July 2024. Project page: https://physics. al
com/
[3] Josh Alman and Hantao Yu. Fundamental limitations on subquadratic alternatives transform- ers. arXiv preprint arXiv:2410.04271, 2024.
[4] Simran Arora, Sabri Eyuboglu, Aman Timalsina, Isys Johnson, Michael Poli, James Zou, Atri Rudra, and Christopher Ré. Zoology: Measuring and improving recall in efficient language models. arXiv preprint arXiv:2312.04927 2023.
[5] Maximilian Beck, Korbinian Pöppel, Markus Spanring, Andreas Auer, Oleksandra Prudnikova, Michael Kopp. Günter Klambauer, Johannes Brandstetter, and Sepp Hochreiter. xlstm: Extended long short-term memory. arXiv preprini arXiv:2405.0455 004511 2024.
[6] Ali Behrouz, Peilin Zhong, and Vahab Mirrokni. Titans: Learning to memorize at test time. arXiv preprint arXiv:2501.00666 2024.
[7] Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou. Birth of transformer: memory viewpoint. Advances Neural Information Processing Systems, 36:1560-1584 1588, 2023.
[8] Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al. Piqa: Reasoning about phys- ical commonsense in natural language. In Proceedings of the AAAI conference artificial intelligence, volume 34, pages 7432-7439, 2020.
[9] Tom Brown, Benjamin Mann. Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-19011, 2020.
[10] Hila Chefer, Shir Gur, and Lior Wolf. Transformer interpretability beyond attention visualization. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 782-791, 2021.
[11] Christopher Clark, Kenton Lee, Ming- Wei Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova. Boolq: Exploring the surprising difficulty of natural yes/no questions. arXiv preprint 190.v:1955.10000 2019.
[12] Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv preprint arXiv:1803.0 0110.880005577 2018.
[13] Vanya Cohen and Raymond Mooney. Met-benchi Multimodal entity tracking for evaluating the limitations of lision-language and reasoning models. arXiv preprint arXiv:2502.10886, 2025.
[14] Laszlo Csanky. Fast parallel matrix inversion algorithms. In 16th Annual Symposium on Foundations of Computer Science (sfcs 1975), pages 11-12. IEEE, 1975.
[15] Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. arXiv preprint ww.Xiv:2377.08611 2023.
[16] Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Uni- versal transformers. arXiv preprint arXiv:1807.033: 00890.3...99.. 2018.
[17] Grégoire Delétang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, et al, Neural networks and the chomsky hierarchy, arXiv preprint arXiv:2207.02000 2022.

---

[18] Yihe Dong, Jean-Baphen Baptiste Cordonnier, and Andreas Loukas, Attention is not all you need: Pure attention loses rank doubly exponentially with depth. International conference on machine learning, pages 2793-2803. PMIR, 2021.
[19] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. 1929,, 2020.
[20] Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, al. The Ilama 3 herd of models. arXiv preprint arXiv:2407.21783 2024.
[21] Nelson Elhage, Tristan Hume, Catherine Olsson, Neel Nanda, Tom Henighan, Scott Johnston, Sheer ElShowk, Nicholas Joseph, Nova DasSarma, Ben Mann, Danny Hernandez, Amanda Askell, Kamal Ndousse, Andy Jones, Dawn Drain, Anna Chen, Yuntao Bai, Deep Ganguli, Liane Lovitt, Zac Hatfield-Dodke Jackson Kernion, Tom Conerly, Shauna Kravec, Stanislav Fort, Saurav Kadavath, Josh Jacobson, Eli Tran-Johnson, Jared Kaplan, Jack Clark, Tom Brown, Sam McCandlish, Dario Amodei, and Christopher Olah. Softmax linear units. Transformer Circuits Thread, 2022. ttap://transformer-rrruuu wiw.uiss..ub222222ssl/neee... pubb20022/souu//ddexxh..m
[22] Nelson Elhage, Tristan Hume, Catherine Olsson, Nicholas Schiefer, Tom Henighan, Shauna Kravec, Zac Saatficd-DDole Robert Lasenby. Dawn Drain, Carol Chen, Roger Grosse, Sam McCandlish, Jared Kaplan, Dario Amodei, Martin Wattenberg, and Christopher Olah. Toy models of superposition. Transformer Circuits Thread, 2022. https:/transsormer- circuits.pub/2022/on htwp://00022oooooe///eeeeee...e model/mndex..inee
[23] Nelson Elhage, Neel Nanda, Catherine Olsson, Tom Henighan, Nicholas Joseph, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, et al. A mathematical framework for transformer circuits. Transformer Circuits Thread, 1(1):12, 2021.
[24] Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective. Advances in Neural Information Processing Systems, 36:70757-70798, 2023.
[25] Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems, 35:30583-30599 2022.
[26] Angeliki Giannou, Shashank Rajput, Jy-yong Sohn, Kangwook Lee, Jason D Lee, and Dimitris Papailiopoulos. Looped transformers as programmable computers. In International Conference on Machine Learning, pages 11398-1141 11442. PMLR, 2023.
[27] Riccardo Grazzi, Julien Siems, Arber Zela, Jörg KH Franke, Frank Hutter, and Massimiliano Pontil, Unlocking state-tracking in linear rnns through negative eigenvalues. arXiv preprint arXiv:2411. 2024.
[28] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00755 2023.
[29] Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, et al. Deepseek-rl: Incentivizing reasoning capability in Iims via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025.
[30] Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed BI-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Camey,, et al. Openai ol system card, arXiv preprint arXiv:2412.16720. 2024.
[31] Samy Jelassi, David Brandfonbrener, Sham M Kakade, et al. Repeat after me: Transformers are better than state space models at copying. In Forty-first International Conference on Machine Learning, 2024.
12

---

[32] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger. Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek. Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. nature, 596(7873):583-588, 2021.
[33] Jikun Kang, Wenqi Wu, Filippos Christianos, Alex Chan, Fraser Greenlee, George Thomas, Marvin Purtorab, and Andy Toulis. Lm2: Large memory models. arXiv preprint arXiv:2502.06044 2025.
[34] Jinwoo Kim, Dat Nguyen, Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Se- unghoon Hong. Pure transformers are powerful graph learners. Advances in Neural Information Processing Systems, 35:14582-14595, 2022.
[35] Aonian Li, Bangwei Gong, Bo Yang, Boji Shan, Chang Liu, Cheng Zhu, Chunhao Zhang, Congchao Guo, Da Chen, Dong Li, al. Minimax-01: Scaling foundation models with lightning attention. arXiv preprint arXiv:2501.088) 2550,08313, 2025.
[36] Yingcong Li, Muhammed Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. Trans- formers as algorithms: Generalization and stability in-context learning. In International conference on machine learning, pages 19565-19594. PMLR, 2023.
[37] Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv preprint arXiv:2402./2872 1, 2024.
[38] Opher Lieber, Barak Lenz, Hofit Bata, Gal Cohen, Jhonathan Osin, Itay Dalmedigos, Erez Safahi, Shaked Meirom, Yonatan Belinkov, Shai Shalev-Shwards et al. Jamba: A hybrid transformer-mant mamba language model. arXiv preprint 2.XXx::2403.988877 2024.
[39] David Lindner, János Kramár, Sebastian Farquhar, Matthew Rahtz, Tom McGrath, and Vladimir Mikulik. Tracr: Compiled transformers as a laboratory for interpretability. Advances in Neural Information Processing Systems, (6:37876-37899 2023.
[40]
Jack Lindsey, Wes Gurnee, Emmanuel Ameisen, Brian Chen, Adam Pearce, Nicholas L. Turner, Craig Citro, David Abrahams, Shan Carter, Basil Hosmer, Jonathan Marcus, Michael Sklar, Adly Templeton, Trenton Bricken, Callum McDougall, Hoagy Cunningham, Thomas Henighan, Adam Jermyn, Andy Jones, Andrew Persic, Zhenyi Qi, T. Ben Thompson, Sam Zimmerman, Kelley Rivoire, Thomas Conerly, Chris Olah, and Joshua Batson. On the biology of a large language model. Transformer Circuits Thread, 2025.
[41] Ashok Vardhan Makkuva, Marco Bondaschi, Adway Girish, Alliot Nagle, Hyeji Kim, Michael Gastpar, and Chanakya Ekbote. Local to global: Learning dynamics and effect of initialization for transformers. Advances in Neural Information Processing Systems, 37:86243-8638
2024.
[42] William Merrill, Jackson Petty, and Ashish Sabharwal. The illusion of state in state-space models. In International Conference on Machine Learning, pages 35492-35506. PMLR, 2024.
[43] William Merrill and Ashish Sabharwal. The expressive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923, 2023.
[44] William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers. Transactions of the Association for Computational Linguistics, 11:531-545, 2023.
[45] Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. Can suit of armor conduct electricity? a new dataset for open book question answering. arXiv preprint arXiv:1809.08 1809.02789) 2018.
[46] Tomas Mikolov, Martin Karafíát, Lukas Burget, Jan Cernocký, and Sanjeev Khudanpur. Re- current neural network based language model. In Interspeech, volume 2, pages 1045-1048. Makuhari, 2010.
[47] Alireza Hosssvv, Clayton Sanford, Denny Wu, and Murat A Erdogdu. When do transformers outperform feedforward and recurrent networks? a statistical perspective. arXiv preprint arXiv:2503.11277 2025.
13

---

[48] Xueyan Niu, Bo Bai, Lei Deng, and Wei Han. Beyond scaling laws: Understanding transformer performance with associative memory. arXiv preprint arXiv:2405.08777. 2024.
[49] Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, et al. In-context learning and induction heads. arXiv preprint arXiv:2209.11 18955 2022.
[50] Denis Paperno, Germán Kruszewski, Angeliki Lazaridou, Quan Ngoc Pham, Raffaella Bemardi, Sandro Pezzelle, Marco Baroni, Gemma Boleda, and Raquel Fernández. The lambada dataset: Word prediction requiring broad discourse context. arXiv preprint 1o6iv:160600603/ 2016.
[51] Bo Peng, Eric Alcaide, Quentin Anthony, Alon Albalak, Samuel Arcadinho, Stella Biderman, Huanqi Cao, Xin Cheng, Michael Chung, Matteo Grella, et al. Rwkv: Reinventing mns for the transformer era. arXiv preprint arXiv:2305.13044 2023.
[52] Bo Peng, Ruichong Zhang, Daniel Goldstein, Eric Alcaide, Haowen Hou, Janna Lu, William Merrill, Guangyu Song, Kaifeng Tan, Saiteja Utpala, et Rwkv-7" goose" with expressive dynamic state evolution. arXiv preprint arXiv:2503. 14456, 2025.
[53] DL Prados and SC Kak. Neural network capacity using delta rule. Electronics Letters, 25(3):197- 199, 1989.
[54] Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan, Lingpeng Kong, and Yiran Zhong, cosformer: Rethinking softmax in attention. arXiv preprint arX19:2202.08791, 2022.
[55] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference machine learning, pages 8748-8766 8763. PmLR, 2021.
[56] Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever. Robust speech recognition via large-scale weak supervision. In International conference on machine learning, pages 28492-28518, PMLR, 2023.
[57] Siva Reddy, Danqi Chen, and Christopher D Manning. Coqa: A conversational question answering challenge. Transactions of the Association for Computational Linguistics, 7:249-266, 2019.
[58] Liliang Ren, Yang Liu, Yadong Lu, Yelong Shen, Chen Liang, and Weizhu Chen. Samba: Simple hybrid state space models for efficient unlimited context language modeling. arXiv preprint (tl.:2406.07522.. 2024.
[59] David E Rumelhart, Geoffrey E Hinton, Ronald J Williams, et al. Learning internal representa- tions by error propagation, 1985.
[60] Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge at scale. Communications of the ACM, 64(9):99-106, 2021.
[61] Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms. Advances in Neural Information Processing Systems, 37:78320-78370. 2024.
[62] Maarten Sap, Hannah Rashkin, Derek Chen, Ronan LeBras, and Yejin Choi. Socialiqa: Com- monsense reasoning about social interactions. arXiv preprint arXiv: arXiv:1904. 09728, 2019.
[63] Imanol Schlag, Kazuki Irie, and Jürgen Schmidhuber. Linear transformers secretly fast weight programmers. In International conference on machine learning, pages 9355-9366. PMLR, 2021.
[64] ByteDance Seed, Yufeng Yuan, Yu Yue, Mingxuan Wang, Xiaochen Zuo, Jiaze Chen, Lin Yan, Wenyuan Xu, Chi Zhang, Xin Liu, et al. seed-thinking-vl. 5: Advancing superb reasoning models with reinforeement learning. arXiv preprint arXiv:2504.1399 2025.
14

---

[65] Darsh J Shah, Peter Rushton, Somanshu Singla, Mohit Parmar, Kurt Smith, Yash Vanjani, Ashish Vaswani, Adarsh Chaluvaraju, Andrew Hojel, Andrew Ma, et al. Rethinking reflection in pre-training. arXiv preprint arXiv:2504.04000 2025.
[66] Julien Siems, Timur Carstensen, Arber Zela, Frank Hutter, Massimiliano Pontil, and Riccardo Grazzi. Deltaproduct: Improving state-tracking in linear rnns via householder products. arXiv preprint arXiv:2502. 10297, 2025.
[67] Gregory O Stone al. An analysis of the delta rule and the learning of statistical associations. Parallel distributed processing: Explorations in the microstructure of cognition, 1:444-459, 1986.
[68] Yutao Sun, Li Dong, Shaohan Huang, Shuming Ma, Yuqing Xia, Jilong Xue, Jianyong Wang. and Furu Wei. Retentive network: A successor to transformer for large language models. arXiv preprint arXiv:2307.0862/ 2023.
[69] Martin Sundermeyer, Ralf Schlüter, and Hermann Ney. Lstm neural networks for language modeling. In Interspeech, volume 2012, pages 194-197, 2012.
[70] Yuandong Tian, Yiping Wang, Zhenyu Zhang, Beidi Chen, and Simon Shaolei Du Joma: Demystifying multilayer transformers via joint dynamics of mlp and attention. In The Twelfth International Conference on Learning Representations, 2024.
[71] A Vaswani. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
[72] Ke Alexander Wang, Jiaxin Shi, and Emily B Fox. Test-time regression: unifying framework for designing sequence models with associative memory. arXiv preprint arXiv:2501.12352 2025.
[73] Xiaoqiang Wang, Suyuchen Wang, Yun Zhu, and Bang Liu. R'mem: Bridging memory retention and retrieval via reversible compression. arXiv preprint arXiv:2502. / 15957, 2025.
[74] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
[75] An Yang, Baosong Yang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Zhou, Chengpeng Li, Chengyuan Li. Dayiheng Liu, Fei Huang, et al. Qwen2 technical report. arXiv preprint arXiv.2407106771 2024.
[76] Songlin Yang, Jan Kautz, and Ali Hatamizadeh. Gated delta networks: Improving mamba2 with delta rule. arXiv preprint arXiv:2412.06466 2024.
[77] Songlin Yang. Bailin Wang, Yu Zhang, Yikang Shen, and Yoon Kim. Parallelizing linear transformers with the delta rule over sequence length. arXiv preprint arXiv:2406. 244444444 2024.
[78] Andrew C Yao. Circuits and local computation. In Proceedings of the twenty-firs annual ACM symposium on Theory of computing, pages 186-196, 1989.
[79] Yang Yue, Zhiqi Chen, Rui Lu, Andrew Zhao, Zhaokai Wang. Shiji Song, and Gao Huang. Does reinforcement learning really incentivize reasoning capacity in lims beyond the base model? arXiv preprini arXiv:2504. / 38337, 2025.
[80] Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar. Are transformers universal approximators of soquence-to-sqqenne functions? arXiv preprint arXiv: 10077, 2019.
[81] Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can machine really finish your sentence? arXiv preprint arXiv:1905.0783 2019.
[82] Yufei Zhao. Probabilistic methods in combinatorics. com/pm, 2022.
Draft available at https:/yyufeicho..
[83] Hanlin Zhu, Shibo Hao, Zhiting Hu, Jiantao Jiao, Stuart Russell, and Yuandong Tian. Reasoning by superposition: A theoretical perspective on chain of continuous thought. arXiv preprint 1rX5v 2025.
15

---

A Delta Rule with Kernel Function
We consider the kernel function x(x, y) = (xx)" ( where (xx) is mapping from d to infinite dimensions. Then the delta-rule-based update form and the corresponding read-out equation can be re-write as:
S.
+ (ks)
(12)
0t S.((4))
(13)
Hypothesis:
S Σ u.w
(14)
where u, and wi pending. Then we have:
umii (1 - (()))))))))) o
(15)
j.ui u (-b))))((ka))) wx)((())
(16)
take the pending w/ = (kaa):
uk+b(k+)
(k:)) (-v())))( + (ka()
(k:) (b)k)) (ke)
(k+) Th + t. ((ki)
(17)
Thus, we get the pending uy:
7 (KA) =
(kk) (kkk)s + + Toto
(ki k)) + ni-
(18)
Then we have the final update form and the corresponding read-out equation:
S
Tkk) = S T +
(19)
(ki,, g.)u..
(20)
B Proof of Theorem 1
Before proving Theorem
introduce auxiliary lemma for facilitating the proof.
Lemma Consider Theorem 7 the set of keys {kr) satisfies Assumption I, and lizn is the difference between two keys chosen from (k:) 1a the function f(:) satisfies Assumption
2, then the following identity holds:
V1 HI 1121:
f((k: - ky) = f(k kt) - -(kk kt).
16

---

B.0.1 Proof of Lemma 1
We distinguish two separate cases according to the value of the index 1:
Case 1: S 1 n. Consider the following subcases:
If K; = kt, then we obtain
f((k; 1;)) k1) f(1 ((UL,)))
[(: kt) [1kk ki) - (-U(((()))) =1.
ii. k, kg, then we have
f((ks - -:)) [,) k1) = f(k, ly - 1) f(U(-1,e))
f(::] Ra)) - 5(: Ra) = -1
iii. If + ki Kg Ki, then
( f((k; - Ti) = f(k: kk) = (OU 2c)) =
f(k) h2) - -(U0,)))))((( =0
Case 2: 1 n. In this case, denote kn = ki, kigs where 1 11 <4 S n. Consider the following
possibilities regarding the number of equalities among indices i, and 1 12:
If no pair among (i,j) and (4,, (2) is equal, then we have
[((k: ky) T k)) ((U(0, = S k2) [(k ka) ((U(0,,))) ((U(O, O. ii If exactly one pair is equal, we analyze further:
If 4, then we have
f((k: k;) f(U(L,3E)) =
f(k, k4) f(k] k4) -(U(L,))))f(C)) ((U((, 2c)) 1.
2. If -22, then we have
5(1k: kj) = -(U((-1,3)) =-1
f(k k2) f(k] ka) f(U(-1,)) (O, 2c)) -11
j = l,, then similarly
ʃ((k: - -kkk-k,)TToa Tb) = -(U((-,,3))
S(K kt) - 1(k, kn) = -S(U(0,2))) S(U(1,))) = -1
4. j = 12, then similarly
f((k: = =1
f(R k)) - f(k] = -(U(-1,e)) =
iii. If pairs equal simultaneously:
1. If = h, l2, we have
5((k: - ki) F(U()2())) =
- s(U(-1,<)) = f(k: kv) s(k} hz) = (UU(,)))-UU(-1,)))
2. If = 12,= 4, this contradicts the ordering condition j < < 1l and thus cannot occur.
Combining all the above cases, we have completed the proof.
17

---

B.0.2 Formally Prove Theorem 1
We use mathematical induction to prove Theorem
When = n + 1:
h = kit
kit:
(21)
1-1
"t
f(k; ks k2)b = -26 + ue2
(22)
m
we read the state at 4, i.e. 9t = kt1
Σ E((Tkk) un +(- u2a) Uta
(23)
1=1
If we read the state at 12, i.e., q kig
Σ
Σ s(hT uee + (ue, Ut2) Ues
(24)
If we read other states, i.e., the state j. where j + ti, 12.
f(J Σ kk),, un-
(25)
In summary, at step ( - n + 1, according our rules, is possible to trace the states exchanged between l and 12.
Assuming the proposition holds for t - 1, we consider the case for (t > + 1).
At the t-th step.
hec Kr, K22
(26)
According to Lemma I, we have
Ue f(K ko)k
Σ ((oT) Σ kini,ki)u
Üc, + t
(27)
If we read the state at t1, i.c., gt ke.,
flat k:)
k:),
= Σ f ks kus + f(kT) ke)u
Ur + (-or, + Ttz) Uta
(28)
18

---

If we read the state at tg. i..., 98 = -129
Σ Mle ki)us
= Σ ks)us + KKk
U12 + (oe, dta)
Ut.
(29)
If we read other states, i.c., the state at j. where j # tı, 22.
Σ
f(
ks) Σ [(k} ks)ws
1=1
Σ S(k) ki)u; ; S(K] ka)ue
1=1
(30)
In summary, at step i, according to our rules, the retrieved states corresponding to (k kn is correct.
By mathematical induction, regardless of how large the exchange step is, the model can always trace the exchange of states.
B.1 The expression of nonlinear vs linear
also conducted stress tests on the round and linear function in this Section, with 128. The setting is similar to Section 4.1 but with experiments where is greater than equal to 128. We use n {128, 256, 512), and the corresponding training length (256, 512, 1024) to ensure as much as possible that most elements participate in the exchange. In addition, to avoid optimization issues, adopted the almost orthogonal vectors used in our Theorem to set key and value of the model and the model only needs to learn to read information from the state space. The results is shown in Figure
(a) d 128, 128.
(b) d 128, 256.
(c) d 128, 512.
Figure 6: Comparison of DeltaFormer with k(x, 9) x y and <(x, v) T y1.
We can observe that when d is fixed, severely degraded. This essentially involves the famous Thompson problem, which is how to place many orthogonal vectors as possible the d-dimensional unit sphere. However linear functions cannot have superposition, and nonlinear functions can store a large amount of information through superposition 22
d increases, the performance of the linear kernel is
C Compare of linear version and no-linear version of Theorem I
Theorem (rephrased) Let the list be [1,2... (1.,...., ... n). ...,, Define the swap operation Gt,; as
LÍi, k = i,
L[i]. k= j. L[k), otherwise.
19

---

Let sequence of swaps be 91. .2......9.. E G = G.. 0 < S n). Then there exists single-layer DeltaFormer F with head dimension (log n) such that
... - 91 o g2 0.... 9: (L)
KU Cache read out and rewrite
We can introduce the KU cache compress operator ku(-) that pre-fills the sequence .)..... into cache of size (n n), independent of With this cache obtain another single-layer
DeltaFormer H satisfying
= Flg .1.55).......
Comparison with Lemma 2 in RWKV-7
Lemma 2 in RWKV-7 (rephrased) There exists single-layer RWKV-7 block F
head dimension O(n),
state-space size Onn?),
such that
P(g1.....9t.3) 91 o ..... gi (L)
D
What language can DeltaFormer express?
Regarding the expressive power of models, addition to computational complexity theory, can also be understood from the perspective of language hierarchy. We conducted an experiment on language hierarchy, and the results are shown in Table The results show that in the category of regular (R) language, Deltaformer has better length generalization ability compared to Transformer, indicating that Deltaformer can learn circuits that are easily length generalized compared Transformer. But for some more complex languages, such deterministic context-free (DCF) and context-sensitive (CS) languages, the performance of Deltaformer and Transformer is not as good as RNN models, such as Tape-RNN [17]. However, considering that RNN models have not yet been efficiently implemented on GPUs, we believe that DeltaFormer is practical.
Model Architecture
Level
Task
RNN
Stack-RNN
Tape-RNN
Transformer
LSTM
Deltaformer
Modular Arithmetic (Simple)
100,0
100.0
100.0
24.2
100,0
100,0
Parity Check
100.0
100.0
100.0
52.0
100.0
100.0
Stack Manipulation
56.0
100.0
100.0
$7.5
59.1
58.3
DCF
String
100.0
Duplicate String Odds First
100.0
$2.8
54.7
CS
51.0
51.9
100.0
52.8
55.6
52.5
Table 5: Language hierarchy solvable by different model architectures
E
Efficient Chunk-wise Implementation
Below is a simple PyTorch implementation, serving pseudo-code. We can easily modify the selection of the kernel function or remove the normalization term. We tried three different ways of running time on the H100, as shown in Table And we can see that the chunkwise algorithm has a 22x speed improvement compared to the recurrent implementation. At the same time, compared to fully parallel algorithms, it has an 8x speed improvement, because fully parallel algorithms are bounded by I/O, due to the n size matrix. The details can refer to the Readme file in the supplementary materials of the Triton implementation.
20

---

Method
Time
Recurrent
279.9 ms
Parallel
102.2 ms
Chunk-wise
12.7
Table 6: Comparison of execution times with tensor shape [2.32,8192,128] in an H100.
import torch
import torch. nn. functional as F import math
def flash_atth (kunk K_prev, V-prev):
attn c_chunk @ K_prev. transpose (-1, -2) ////math... serttth.qqriie [-1]) 2_intra torch. logsumexp (attn, dim=-1)
sqrt (K_ chunk shape
return forch.softmen (attn dim=-1) z_intra
def beive_iiplementation actually new v.
n, d_model): """n is the previous v, v
B, H, т, D shape
torch. zeros (n)
t range (T): if == 0:
v[:, 0] n(: :, 0]
else:
scores torch. matmul i i, :t], k[;, ;, t] unsqueeze (-1)) squeeze math sqrt (d_model)
attn_probe F.softmax (scores, dim=-1)
v(:, i, t] nl:, :, t] torch. sum (attn unsqueeze
(-1) * vl;, it], dim--2)
return
def
optimized_ chaellchccee..cc implementation(K, N, d_model, C): B, н, т, D K. shape
v torch. zeros (B, H, D) chunk_nums mask torch.tri (torch, ones (c, c) diagonaal=-1) unsqueeze (0). unsqueeze (0) to (K. device)
//
for chunk_nur in range (cchun_nummss)
start chunk_num end (chunk_num 1)
K_chunk k[;, :, start:end]
R_chunk M[;, ;, start:end]
if chunk_num 0:
intra_output, Z_intra flash ch_ckun,, K[:, ;, :start J. vl:, ;, staatt))0(TTO) A = (K_ckunk @ K_chunk. (-22,, - masked_ (mask
[: :, :c] == 0, float ('oinf"))f"))
math m (d_ (d_mode]) #C Z_ inter torch logsumexp (A, dim=-1)
N_ chunk intra_output
(1/(1 torch. exp (Z_inter-
2_intra) unsqueeze (-1))))
A = F. softmax (A, dim=-1) * (1/(1 torch exp (itra- 2_inter) unsqueeze (-1))))
A[:,;,0,;
else:
A = (K_chunk @ K_chunk, transpose (-2, [;, :,, :c] == 0, float ("-inf")) / math sqrt (d_model)
fill (mask
(A dim=-1) A[:,;,0,;] P N_chunk
Ti torch. eye (C). unsqueeze (0). unsqueeze (0). unsqueeze (0). to (K.
device)
21

---

тi_ inverreeee = torch inverse ## Forward substitution method (CC33) Each block be solved in parallel if don't ot the normalization of softmax.
v(:, ;, start:end) Ti_inverse P # 2DC return V #0(T/C (TCD + c>2D)) O(T-2D + TCD + TC
def verity_equivalencee
и 2
I = 1024
64
32
torch. randn H, T, D)
N corch.randae H, Т, D)
naive_outpen save__implementationn.. (K, N, D)
ingp equivalence torch. allclose (naive_outpurs optimized atol =le-5)
outimized_output
D, C)
print (fint("" (equivvllllll))))
Listing 1: PyTorch-style pseudo-code.
F
The stability of the calculation of u and o
We rewrite the calculations for and as follows:
= A
A2u,
(31)
where (i(1,) m1,, ky), A2(i, = K2 (k),
Then will have:
[I(A1 +
11 |||
(32)
and
[I + AA2JU - A |( < ||Ai|||U|]].
(33)
The stability of the calculation for u is weaker than that for o, so the selection of the kı need to balance stability and expressivity.
G Code for synthetic data.
Here provide code for synthesizing data and the encoding of input information.
G.1 Track the Exchange of Elements.
import numpy import random
n_elements swap-pairs [(i, j) for i in range (n_elements) for j in range (i+1, n_elements)]
def swply_swap (perm, swap_idx):
i, j = lapp_pairslawap.idx
perm = list (perm)
perm[il, perm[j] perm [j], perm [i]
return tuple(perm)
def generate_des data (k, num_samples):
data
[]
22

---

4
Swap [1. 2]
Swap [2. 4]
Figure 7: Swap task diagram. the beginning, tokens of different colors placed positions to
5, and the tokens of two positions are exchanged at each step. We expect the model to query what the token for each position the token at the first position to avoid introducing qqery token". This task can also be tokenized into a task with input vocabulary size of C5 10 and an output vocabulary size of
each step. Simply but without loss of generality, we default outputting
for range (num_samples):
aequeee [randon randint (0, len (svap_pairs) -1) for in range (k)]
current_perm tuple (rangenn (n_elements))
first_elements []
for awap_idx in wwap_aequence:
current_pera = apply swap (current_perp) swap_idx)
first_elemente apppend
append (current_perm) [0])
input_ids ids torch tensor (svap_sequence, dtype=torch long)
labels torch tensor (first_elements dtype=torch.
data append ( ((input_ids, labels))
return data
G. Reachability of directed acyelic graphs.
1
2
30
4
31
Can reach or not
28
29
Figure 8: Reachability of directed acyelic graphs. Each node encodes most its neighboring node information at the beginning. Then the model need determine whether a node can reach from starting point.
import numpy import random
import torch nn as nn def Sreaategraah(n if n % 2 1= 0: raise ValueError ("n should be even number")
Step 1: Randomly divide the points into two sets s.1 and $_2 points list (range n + 1))
random. shuffle (points)
mid //
s_1, $_2 sprint
sorted (points [mid:])
def (s) parents (
23

---

for in range(1, (
possible_parents
parents S[:i]
parents [S[i]] random. choice [possible_parents) return parents
Step 2: Assign parent nodes within each set
parenta_St $1 assign.parenta (8_1)
parenta_S2 aesign.parenta (S_2)
Step 3: Build adjacency matrix adjacency.matrad def silL_aajacency.aaaii
eye(n)
for child, parent in parents items ()
if parent is not None: adjacacyy.atrrix(chid 1p 1]
catennc_matrizeo (parenta_ $2)
labels [o for 1 in range(n)] if 1 in 8_1:
in 8.1: labels[i-1]
else:
for i in $_2: labels[i-1]
return labels, adjacency.matrix
def Sanerate_graphddee data (num sam_samples--00, n=32)
Generates graph
samples
reachability information.
param num_ num_samples: Number of samples to generate.
param n: Number of nodes in the graph.
return: A list of tuples. Each tuple contains adjacency matrix a list labels indicating reachability from node 1 each node.
data = []
for range (num (num_samples):
labels,
create-graph (n)
adj_matrix = torch. (An dtype=torch.fll float) # adj_matrix
adj_matriz (oanspose
labels corch.tensen (labels, dtype long) data append append (adi_matrrx, labels))
return data
cl ass Emb (nn Module): #Encode the neighbor node information of each node and mark the starting point
def __init__ (self, config): super (n..ini). self hiddensizee config. hidden_size def forward x);
# shape: (batch_size, seq_len, input_dim) batch_size, seq_len, input_dir. x.shape pos onehot torch. zeros
seq_len, device=x, device)
[os_onehot 0] = # Mark the starting point
pos_emb pos_on www.oomooouuuuuseeeeeeeeee... (0) expand (batch.sizeee -1, -1) (batch_size, seq_len, seq_len)
current_dim = x.size
if current_dim hel.f.idden hiddeh_didnnsee
pad_size pad_size [-1] self.hidden_siz current_dim
padding torch (erad device=x.device x torch... torch.cat cāx, padding], dim=-1) (batch_size, seq_len, (izden_sizee) return x to
24

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will published with the paper.
The reviewers of your paper will be asked use the checklist as one of the factors their evaluation. While "[Yes] is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] providedd proper justification is given (e.g.. "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering binary way, we
"[No] or "[NA]" is not grounds for rejection. While the questions are phrased acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes. At the last of introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in 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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes. There is a limitation section.
25

---

Guidelines:
The answer NA means that the paper has no 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 their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, 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 a 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 to 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 fairesss.
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 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?
Answer: [Yes]
Justification: There is two assumption in main text. And the complete proof is in Appendix.
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 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 short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or 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 of 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: [Yes]
Justification: We use open-source code for the training of language model and offer code for toy tasks we design.
Guidelines:
The answer NA means that the paper does not include experiments.
26

---

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 is specific model and empirical evaluation, it may be necessary to either make 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
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) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily 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 an open-source dataset instructions for how to 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 reproducibilityy 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
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We use open-source data. The synthetic data for the toy task can be found in the supplementary materials.
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, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.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 NeurIPS code and data submission guidelines (https
//nips.cc/public/eee.c www.ddddeeeooeuummmmccco ssi 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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
27

---

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
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification:
We offer it in jupyterbook in supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core 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, 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: [Yes]
Justification:
We just average over 3 runs for language modeling.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror 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.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state 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 out of range (e.g. negative error rates).
If error bars reported in tables or 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 on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We offer in main text.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
28

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics ltttp::/neurips: httppp/c...pppp.iiicccccccccaeea
Answer:
[Yes]
Justification: We made sure to preserve anonymity.
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 circumstances that require a deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in 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:
We study the structure of models, which has societal impact.
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 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.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [No]
Justification: We use public datasets from the Internet.
Guidelines:
The answer NA means that the paper poses such risks.
29

---

Released models that have high risk for misuse or dual-use use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to 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. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We CC-BY 4.0 in code.
Guidelines:
The answer NA means that the paper does not use 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 (e.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 /dtaaset 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 has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We communicate the details the dataset/code/moodl at the supplementary
materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing 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 as details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
30

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information 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 to the NeurIPS Code Ethics, workers involved in data collection, curation, 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 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: the paper does not involve crowdsourcing nor research with 780 human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on 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 we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMS if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [Yes]
Justification: LLM is used only for writing, editing.
Guidelines:
The answer NA means that the core method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: //tpa:://///////// cc/ /oonferennces/2225. for what should or should be described.
31


Reviews:
[{"review_id": "Rpm0PwWVox", "reviewer": "Reviewer_cP7d", "summary": "This work introduces DeltaFormer, an extension of the delta rule using kernel functions in order to increase the expressive power of standard Transformers. By incorporating nonlinear functions, the authors show that DeltaFormer can learn state-tracking tasks such as swapping elements in a sequence, while maintaining competitive performance in language modeling tasks compared to standard Transformers.", "questions": "- Which similarity function did you use in the language modelling experiments?\n\n-- References --\n\n[1] Songlin Yang, Bailin Wang, Yu Zhang, Yikang Shen, and Yoon Kim. Parallelizing Linear Transformers with the Delta Rule over Sequence Length. Advances in Neural Information Processing Systems, 36, 2024\n\n[2] R. Grazzi, J. Siems, A. Zela, J. Franke, F. Hutter, and M. Pontil. Unlocking State-Tracking in Linear RNNs Through Negative Eigenvalues. In The Thirteenth International Conference on Learning Representations (ICLR’25). ICLR, 2025.\n\n[3] Gregoire Deletang, Anian Ruoss, Jordi Grau-Moya, Tim Genewein, Li Kevin Wenliang, Elliot Catt, Chris Cundy, Marcus Hutter, Shane Legg, Joel Veness, et al. Neural Networks and the Chomsky Hierarchy. In The Eleventh International Conference on Learning Representations, 2023.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:**\n- The paper proposes a new model that increases the expressivity of Transformers by applying the delta rule on the kernel space.\n- The new architecture is comparable on language modelling tasks with standard Transformer models, while achieving better performance on a state-tracking task, namely permuting elements (swaps).\n- The authors provide an efficient implementation of DeltaFormer.\n\n**Weaknesses:**\n- The authors compare DeltaFormer only to Transformers, however there are several other subquadratic models that are more expressive and excel on state-tracking tasks. Even DeltaNet [1] with negative eigenvalues in the state-transition matrix is able to solve state-tracking tasks such as parity or permutation groups [2] and performs competitively on the same language modelling tasks used in this submission. I recommend the authors to add the results from these methods in their benchmark results.\n- The authors demonstrate increased expressivity only on a single task. I strongly encourage to support the theory with more experiments, e.g. on formal language tasks as proposed in [3].\n- I think evaluating larger models is necessary for wider adoption of DeltaFormer in the long run. The model shows increased expressivity by adding simple similarity functions between keys, however it is not clear how this will impact the performance at larger scale.\n\n*Minor:*\n- Line 210: reference to appendix broken.\n- The figures are sometimes hard to read, especially due to the small font size.\n- For better comparison, I suggest to put all the methods' learning curves on the same plot.", "was_revised": true, "final_justification": "Most of my concerns have been addressed, especially the comparison to other sub-quadratic models, scaling experiments and formal language tasks", "rebuttal": "We sincerely thank you for your insightful feedback. The references you provided were invaluable in deepening our discussion and strengthening the manuscript. In the following, we address each of your concerns in turn.\n\n1.**Regarding other quadratic methods that perform well on state-tracking tasks.**  \nWe agree that certain quadratic alternatives can indeed achieve competitive results on these benchmarks.\n\nA. In the original submission we did not benchmark them exhaustively, because our primary goal was to propose an architecture that improves the *asymptotic* complexity of the Transformer rather than to outperform every quadratic variant on every task. We view these quadratic methods as strong baselines, yet they are ultimately constrained by the same retrieval limitations inherent in the standard attention mechanism.\n\nB. We did, however, include a comparison between linear and non-linear variants in Appendix B.1 (the linear variant can be interpreted as a form of delta rule). As shown there, once the number of elements to be tracked exceeds the head dimension, the linear variant degrades sharply. This observation echoes earlier studies comparing vanilla and linear Transformers: both can retrieve information in principle, but the former remains superior on long-context “needle-in-a-haystack” tasks.\n\nC. To further solidify our empirical results, we augmented the evaluation suite of Paper 2 with the Parity task. The new results are summarized as follow:\n| Model / Variant                              | Parity Accuracy |\n|----------------------------------------------|-----------------|\n| Transformer                                  | 0.022           |\n| Mamba [0, 1]                                 | 0.000           |\n| Mamba [-1, 1]                                | 1.000           |\n| DeltaNet [0, 1]                              | 0.017           |\n| DeltaNet [-1, 1]                             | 1.000           |\n| mLSTM                                        | 0.087           |\n| sLSTM                                        | 1.000           |\n| DeltaFormer – Linear + Softmax,  β ∈ [0, 2]             | 1.000           |\n| DeltaFormer – Softmax + Softmax,  β ∈ [0, 2]             | 0.021           |\n| DeltaFormer – Exp + Softmax,       β ∈ [0, 2]           | 1.000           |\n| DeltaFormer – ReLU + Softmax, β ∈ [0, 2]              | 1.000           |\n| DeltaFormer – Round + Softmax, β ∈ [0, 2]    | 0.037           |\n| DeltaFormer – Round + Softmax, β ∈ [-1, 2]   | 1.000           |\n| DeltaFormer – Round + Round, β ∈ [0, 2]                | 0.041           |\n\n We observe that the choice of kernel function significantly influences DeltaFormer’s performance on Parity. Among the combinations we tested, “round + round” and “softmax + softmax” underperform relative to others. We suspect this stems from optimization difficulties—likely a need for finer-grained hyper-parameter tuning or a re-scaling of the gate range—which we leave to future work.\n\n2.**Additional experiments on formal-language tasks to further support our theory.**\n\nIn the original submission we concentrated on synthetic tasks that capture the strict expressive boundary of TC⁰, specifically accessibility problems on S₅ and directed acyclic graphs (DAGs). This focus allowed us to demonstrate that our architecture can provably exceed this boundary, and we therefore did not include other formal-language benchmarks.\nWe are grateful for the reviewer’s suggestion and the accompanying references. While their official implementation is provided in JAX, our codebase is PyTorch-based; we are currently re-implementing the tasks in PyTorch to ensure full reproducibility and fair comparison. Preliminary runs are under way, and we will update the manuscript with the new results as soon as they are ready—no later than the camera-ready deadline.\n\n3.**Evaluation at larger scale**\n\nWe fully agree that demonstrating scalability is essential for the broader adoption of DeltaFormer. To this end, we trained a 14 B-parameter MoE model with 680 M active parameters on 500 B tokens. The downstream results are summarized as follow:\n\n| Benchmark (accuracy)    | Transformer | DeltaFormer |\n|--------------|-------------|-------------|\n| COPA         | 73.8        | 74.6        |\n| ARC-E        | 80.9        | 82.9        |\n| ARC-C        | 50.8        | 51.2        |\n| PIQA         | 78.2        | 79.4        |\n| C-Eval       | 44.0        | 46.3        |\n| MMLU         | 43.8        | 45.2        |\n| RACE-High    | 48.8        | 49.0        |\n| RACE-Middle  | 62.5        | 62.9        |\n| SIQA         | 55.6        | 54.7        |\n| Winogrande   | 64.6        | 67.2        |\n| **Average**  | **60.3**    | **61.34**   |\n\n| Training Tokens | General Domain (loss) |              | Code Domain (loss) |              |\n|-----------------|----------------|--------------|-------------|--------------|\n|                 | Transformer    | DeltaFormer  | Transformer | DeltaFormer  |\n| 100 B           | 2.06256        | 2.06254      | 1.52628     | 1.48656      |\n| 200 B           | 1.94337        | 1.94336      | 1.42112     | 1.37757      |\n| 300 B           | 1.88013        | 1.87554      | 1.35612     | 1.32587      |\n| 400 B           | 1.83119        | 1.83558      | 1.32285     | 1.29567      |\n| 500 B           | 1.81472        | 1.81032      | 1.31231     | 1.28326      |\n\nAn instructive pattern emerges from the training curves. On the aggregate corpus, DeltaFormer attains a 0.003 lower loss, while incurring ≈3 % more FLOPs. However, on the code subset the gap widens to 0.05. Mean while  DeltaFormer reaches after 300 B tokens the loss the baseline achieves after 400 B tokens. This gain is much more than FLOP increase alone would explain. Under the “compression ≈ intelligence” hypothesis, we therefore expect even larger DeltaFormers to unlock further improvements on reasoning-heavy domains such as code.\n\n4.**Clarifications requested by the reviewers**\n\nWe thank the reviewers for their careful reading and for highlighting points that need further clarity. Below we address the questions.\nabout the language-modeling similarity function. In our language-modeling experiments we adopted the conventional softmax (q kᵀ) attention score because we intentionally designed DeltaFormer such that the standard Transformer is a strict special case. Concretely, if we set β = 0 and α = 1 in Eq. 7 and let the similarity function in Eq. 8 coincide with the standard softmax attention, the update rule collapses to the familiar single-head softmax attention of the Transformer (see the derivation in Appendix C.2). We will make this correspondence more explicit in the revision."}, {"review_id": "KLxor3rLDJ", "reviewer": "Reviewer_WV7U", "summary": "To address the precision-parallelism trade-off, this paper revisits the delta rule through the lens of kernel functions and propose DeltaFormer, a model that implicitly assigns the state space to Transformer. By introducing kernelization, DeltaFormer offers a novel interpretation of delta updating rule, e.g., DeltaNet as a special case that uses a specific similarity function, and further generalizes the operations using separate kernel functions and gates. DeltaFormer demonstrated improved performance over the Transformer in some toy tasks, but only achieved comparable results in small-scale language modeling in this paper.", "questions": "1. Where do state space models, currently gaining attention as recurrent alternatives, fall in Figure 2? According to ‘The Illusion of State in State-Space Models’ paper, are they considered to be in the same category as Transformers?\n2. In the Swap task, is it possible to use the same input and output vocabulary? The phrase “to avoid introducing a ‘query token’” is unclear—could you clarify what this means?\n3. Theorem 1 omits positional embeddings, but later sections favor RoPE or NoPE. Does this imply those methods yield better results? The explanation in Lines 215–220 could be clearer. Also, were the results in Figure 4 obtained without any positional encoding?\n4. Are all models in Figure 6b single-layer? If so, it would help to state this explicitly in the caption (e.g., “DeltaFormer (Single Layer)”).\n5. Line 240: “Therefore, the operation of matrix inversion greatly improves the expressivity of the model.” — This claim needs more elaboration. Why/how does matrix inversion contribute to expressivity here?\n6. While the proposed model underperforms in small-scale settings, the authors suggest potential in industrial-scale applications. However, given that the motivation hinges on increasing model expressivity, shouldn’t some advantage already appear in small-scale experiments?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "- Strengths\n    1. The paper identifies a key limitation in current sequence modeling paradigms and presents a generalized framework that aims to address the issue with a well-motivated approach.\n    2. The model shows promising feasibility in controlled toy tasks, supporting its potential.\n    3. Implementation details, including the design choices for similarity functions and the use of curriculum learning, are well explained and reproducible.\n- Weaknesses\n    1. If DeltaFormer successfully resolves the trade-off it targets, the benefit should also manifest in small-scale language modeling; however, the experiments show no clear improvement over the Transformer baseline.\n    2. The presentation is weak. There are multiple typos (Lines 26, 56, 202), grammatical errors (Lines 188, 215, 236–239), and missing references (Lines 210, 211). Some expressions may even convey the opposite of the intended meaning (e.g., Line 219).", "was_revised": true, "final_justification": "The rebuttal has clarified the paper’s contributions, and I believe its value is now more evident. I maintain my initial score of Accept.", "rebuttal": "We sincerely thank you for the positive assessment of our work and for the detailed, constructive feedback. Below, we try to address each concern in turn and hope our clarifications can solve your concern.\n\n1.**The synthesis task has benefits, but small-scale models do not have significant gains.**\nWe appreciate this important observation. We conjecture that the limited improvements seen in synthetic tasks at small scale stem from two factors:\na) the bulk of the pre-training distribution is dominated by shallow, memorization-heavy patterns, and\nb) the model capacity is insufficient for acquiring the deeper computational primitives that our architecture is designed to exploit.\n\nTherefore, we conducted experiments on a MOE model with 680m activation parameters and 14b total parameters, and trained a total of 500b tokens. The benchmark results are shown below:\n\n| Benchmark (accuracy)    | Transformer | DeltaFormer |\n|--------------|-------------|-------------|\n| COPA         | 73.8        | 74.6        |\n| ARC-E        | 80.9        | 82.9        |\n| ARC-C        | 50.8        | 51.2        |\n| PIQA         | 78.2        | 79.4        |\n| C-Eval       | 44.0        | 46.3        |\n| MMLU         | 43.8        | 45.2        |\n| RACE-High    | 48.8        | 49.0        |\n| RACE-Middle  | 62.5        | 62.9        |\n| SIQA         | 55.6        | 54.7        |\n| Winogrande   | 64.6        | 67.2        |\n| **Average**  | **60.3**    | **61.34**   |\n\n| Training Tokens | General Domain (loss) |              | Code Domain (loss) |              |\n|-----------------|----------------|--------------|-------------|--------------|\n|                 | Transformer    | DeltaFormer  | Transformer | DeltaFormer  |\n| 100 B           | 2.06256        | 2.06254      | 1.52628     | 1.48656      |\n| 200 B           | 1.94337        | 1.94336      | 1.42112     | 1.37757      |\n| 300 B           | 1.88013        | 1.87554      | 1.35612     | 1.32587      |\n| 400 B           | 1.83119        | 1.83558      | 1.32285     | 1.29567      |\n| 500 B           | 1.81472        | 1.81032      | 1.31231     | 1.28326      |\n\nAn instructive pattern emerges from the training curves. On the aggregate corpus, DeltaFormer attains a 0.003 lower loss, while incurring ≈3 % more FLOPs. However, on the code subset the gap widens to 0.05. Mean while  DeltaFormer reaches after 300 B tokens the loss the baseline achieves after 400 B tokens. This gain is much more than FLOP increase alone would explain. Under the “compression ≈ intelligence” hypothesis, we therefore expect even larger DeltaFormers to unlock further improvements on reasoning-heavy domains such as code.\n\n2.**The presentation is weak. **\n\nWe sincerely thank the reviewers for highlighting that the exposition can be improved. In the revision we will perform a full proof-read, restructure several sections for clarity, and add intuitive figures and pseudo-code to enhance overall readability.\n\n3.**Where is the state space model?**\n\nMamba2, retnet, rwkv6, hgrn2 is in the same category as Transformers, Deltanet, rwkv7, gated deltanet is beyond the  category of Transformers. In order to define these methods more clearly, we may also establish another axis regarding memory capacity to isolate transformer and deltaformer from these finite state space methods.\n\n4.**Details about the swap tasks.**\n\nIt is possible to use the same input and output vocabulary, for example, directly using a large vocabulary that includes both input and output vocabulary.  We apologize for not making it clear in the main text about 'to avoid introducing a query token'. The background is that we originally wanted to identify what elements are at each possible position, but in order to express what elements are at each possible position, we need to introduce an additional n tokens to represent what elements are at a certain position now, where n is the number of positions. If we only fixedly query what the current element is at the first position, then there is no need to introduce n additional tokens. This is just a simplification made to reduce the difficulty of learning, but it does not change the position of this task within the parallel complexity class.\n\n5.**About position embeddings.**\nWe did not use any position embedding in Theorem 1. Additionally, we did not use any position encoding in Figure 4. But before conducting actual language modeling, we are curious about the difference between the NoPE used in Theorem 1 and the RoPE used in actual language modeling. Therefore, we conducted the experiment in Figure 5.  The experimental results are also quite interesting, so we have included them in the main text. \nWe can observe that when using RoPE, the model can have faster convergence, but the upper limit is low. If Nope is used, although the convergence is slow, with the help of course learning, the final upper limit is very high. We hope this experiment can spark further discussion on the role of rethinking position encoding.\n\n6.**Figure 6b.**\n\nYes, it's a single layer. We will improve our presentation to make our paper clear.\n\n7.**Why/How does matrix inversion enhance expressivity?**\n\nMatrix inversion broadens the representational power of the model for two key reasons.\n\na.**Complexity-theoretic relevance**  \n   Certain parallel-complexity classes—specifically NL and SL —are characterized by graph-reachability tasks on directed and undirected graphs, respectively. These tasks lie strictly beyond the reach of constant-depth threshold circuits (TC⁰), the class to which standard Transformers are limited.\n\nb.**Algebraic reduction to matrix inversion**  \n   Connectivity queries can be encoded as reachability in the adjacency matrix **A**. The series  \n   $$\n   I + \\beta A + (\\beta A)^2 + \\dots = (I - \\beta A)^{-1} $$\n   converges (for sufficiently small β) and its (i, j) entry is positive iff node *j* is reachable from node *i*. Hence, computing$ (I - \\beta A)^{-1} $ solves the connectivity problem exactly. Because matrix inversion is not in TC⁰, incorporating it equips the model with strictly greater expressive capacity.\n\nIn short, matrix inversion enables the model to solve connectivity tasks that are provably out of reach for pure Transformer architectures, thereby substantiating the claim that it enhances expressivity.\n\n8.**About small-scale experiments.**\n\nSee rebuttal in \"1.**The synthesis task has benefits, but small-scale models do not have significant gains.**\""}, {"review_id": "SKfjfPpC0f", "reviewer": "Reviewer_scvB", "summary": "This paper proposes a new architecture DeltaFormer that draws inspiration from both transformers and DeltaNet. Drawing from the expressivity literature, the authors claim their architecture should have greater expressivity for state tracking, a task shown to be likely beyond transformers. The authors also evaluate their new architecture on targeted synthetic tasks, finding boosts on state tracking and graph connectivity. They also show that their model achieves similar performance to transformers on standard LM evaluations.", "questions": "> Another noteworthy fact is that existing large models have demonstrated amazing reasoning abilities after reinforcement learning [25, 24, 59], recent studies have shown that models have not unlocked new abilities through RL, and their abilities are limited by pre-training [73, 60].\n\nNote that these models being trained with RL are using CoT, which means they have expressive power outside TC0.", "limitations": "As discussed in weaknesses, the paper would benefit from comparing against a hybrid model (simply mixing DeltaNet layers with transformer layers). The presentation of the greater expressivity of DeltaFormer was also unclear, so I am not confident that its ability to solve NC1-complete problems is correct.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n1. This paper addresses the theoretically motivated problem of developing an architecture with expressivity beyond TC0, proposing a new, likely more expressive architecture by integrating DeltaNet with transformers.\n2. The empirical evaluation of the architecture is extensive, spanning both synthetic evaluations on targeted tasks of theoretical interest and general language modeling evaluations.\n\n## Weaknesses\n\n### Missing Baselines and Comparisons\n\nTwo important questions that should be answered to justify a new architecture are its compute efficiency and whether its complexity is justified compared to a simpler approach.\n\nRegarding compute efficiency, DeltaFormer achieves similar numbers to the transformer in Table 1. But how does it compare in compute efficiency, i.e., are the models matched in number of parameters or in FLOPs? If you're adding some more expensive operations like matrix inversion, then it could conceivably have the effect of making the architecture less compute-efficient.\n\nRegarding potentially simpler approaches, ow would DeltaFormer compare, both theoretically and empirically, to the simpler approach of mixing DeltaNet layers with Transformer layers? It would be good to have this comparison, and also potentially consider whether you hypothesize or can theoretically show any expressivity differences between DeltaFormer and a hybrid model. In particular, I think this comparison to hybrid architectures would be important to say something about.\n\n### Clarity and Potential Correctness Issues\n\nFigure 2 is potentially misleading. What does it mean to put LSTMs and RNNs at the level of P? They can't represent all of P, so presumably you intend this to mean they can solve some P-complete problem. If so, you should say this and also add a reference for which P-complete problem can be solved by RNNs.\n\nTheorem 1 is not clear. This part should be reorganized to explicitly state which NC1-complete problem is solvable and how this relates to the construction. The following claim should also be made more precise:\n\n> In summary, as a general form of transformer, DeltaFormer not only does it surpass the inherent TC0 expressivity of the Transformer, but it can also track the exchange of n objects using much smaller state space than models such as RWKV7.\n\nAnother concern is with the experimental setup in the state tracking experiments:\n\n> And the 1-layer 194 DeltaFormer can execute and track the exchange operations of 5 elements. But increasing the number 195 of layers in the transformer did not improve either.\n\nThis is different from the findings here: https://arxiv.org/abs/2503.03961, where Theta(log n) depth allowed transformers to solve A5 up to length n. This suggests that there might truly be optimization issues involved in the failure of the transformers.\n\nRelatedly:\n\n> We speculate that this is likely the fundamental reason why existing large-scale models achieve randomness in entity tracking tasks [12].\n\nThough with log n depth, the mentioned paper shows saturated-attention transformers can express state tracking up to contexts of length n (even if not for very long contexts).\n\n> Due to the fact that matrix inversion is a task within NC2\n\nHow do you know this? Add a proof or reference", "was_revised": true, "final_justification": "As mentioned in my comment below, the new empirical results, isoFLOPs discussion, and careful elaboration of the theoretical results have addressed many of my initial reservations, beyond the lack of a hybrid model baseline. That said, one paper cannot do everything, and I think this paper would still be a valuable data point for the community on the potential of more expressive language models. Ideally, the others should acknowledge the lack of comparison to hybrid models (a simpler way to gain expressivity beyond transformers) as a limitation.", "rebuttal": ""}, {"review_id": "cXlScJab9x", "reviewer": "Reviewer_PXWq", "summary": "This work proposes \"DeltaFormer\", a generalization of previously proposed \"DeltaNet\" sequence models. Concretely, the authors interpret the \"DeltaNet\" state update and readout mechanisms in terms of kernel functions, which allows them to implicitly operate in infinite-dimensional Hilbert spaces. The \"DeltaNet\" equations (5) and (6) are generalised by use of two different kernel functions and two different gates in (7) and (8). The authors show that their method can emulate an ${NC}^1$ complete problem both in theory and experimentally, they propose a chunk-wise parallel algorithm for their method, and they finally test the proposed method on realistic language modelling tasks.", "questions": "I do not have any immediate questions. All addressable points are listed as weaknesses. I hope you find this review constructive.", "limitations": "\"yes\"", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 1, "significance": 1, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n- The method is clearly superior to the transformer on the element exchange state tracking task and DAG reachability. Considering that you found it manageable to conduct medium-scale NLP experiments, it seems that it could maybe be used in larger models too.\n\n- The chunk-wise matrix inversion method could offer a more optimal trade-off between recurrence and parallelism compared to the naive full recurrence. This is clearly applicable to any such linear \"time-mixing\" operator.\n\n- It is an interesting observation that kernel choice influences the performance on synthetic tasks so much more than on more \"natural\" ones.\n\nWeaknesses:\n\n- As a general note, the paper could be written with better style and clarity. For example, lines 32-33 state that \"it has been proven that in the ${TC}^0$ class, chain of thought needs to be utilised to solve problems in larger classes\". I understand that CoT allows log-precision transformers to emulate circuits whose complexity is beyond that of ${TC}^0$. The quoted sentence seems to try to express this, but it is not clearly formulated (**within** ${TC}^0$, CoT is needed **to escape** ${TC}^0$?) . I don't want to penalise non-native speakers for imperfect English; what I am talking about here are incorrectly expressed ideas.\n\n- The paper really could benefit from a report on the speed-up of the chunk-wise matrix inversion method as compared to the recurrent implementation. \n\n- It was not made clear why \"swap\" is ${NC}^1$ complete under ${AC}^0$ reductions. At least you should point to literature showing that the permutation group over 5 elements is non-solvable, hence ${NC}^1$-complete.\n\n- Considering that you generalised the readout function, it would have made sense to ablate the $\\kappa_2$ design on retrieval tasks too.\n\n- It seems that it makes the most sense to simply stick with the linear kernel, in which case we revert back to the standard delta-net.\n\n- The theorems and proofs could be better explained. It took me a disproportionate amount of time to parse. \n\n- There was no comparison to any related work excluding the Transformer in the experimental section.", "was_revised": true, "final_justification": "The authors have shown significant engagement during the discussion period. They have clarified and expanded on a range of important aspects of their work, and I believe that they successfully demonstrated the benefits of their approach. With the large amount of additional work done to the paper, I believe this work now merits acceptance.", "rebuttal": ""}]

Author rebuttal:

Meta-review: This paper proposes a more expressive variant of Transformer that uses the delta rule-based update rule (i.e., DeltaNet), which increases the theoretical expressivity of Transformers beyond TC0. This involves making the DeltaNet-based RNN into an "infinite dimensional" RNN (which is equivalent to a Transformer with a different sequence-mixing mechanism) through the perspective of kernel functions. The model is coupled with a parallel chunkwise algorithm that enables efficient training. Experiments on synthetic and real-world tasks demonstrate the effectiveness of this new Transformer variant.

On the plus side, the work overcomes an important (theoretical) limitation of Transformers, and is backed up by solid empirical experiments as well as efficient training algorithms. The idea itself is also novel and well executed. On the negative side, there were some baselines that were lacking, and many reviewers noted that clarity/presentation could be greatly improved. Some of these issues were addressed during the rebuttal, and all reviewers were unanimous in recommending acceptance. I concur. (The nontrivial issues that remain with regard to presentation prevent me from recommending a higher rating.)
Decision: Accept (poster)