DeltaFormer: Unlock the state space of Transformer

7. There was no comparison to any related work excluding the Transformer in the experimental section.

a) Yes, that was our initial consideration.
We believed that for highly non-linear RNNs, their performance in state-tracking related tasks would be satisfactory. A significant advantage for Deltaformer would become apparent through comparisons in retrieval tasks. However, since retrieval tasks are not the main focus of this paper, we did not extend our comparisons beyond Transformer-based models.

b) We are, however, very grateful for your insightful feedback. It highlighted the considerable value of conducting a more extensive comparison, which led us to perform experiments on synthetic datasets. The experimental outcomes are presented below:

c) The reason we couldn't compare on language modeling tasks is that models around 400M are too small and exhibit significant bias, leading to unreliable experimental results. Larger-scale experiments would require more computational resources and infrastructure adaptation. Therefore, we only trained a 14B total-activation MoE model for 500B tokens to compare Transformer and Deltaformer. The experimental results are as follows, and we hope they provide some insight.

Benchmark (accuracy)

Training Tokens & Loss

a) Firstly, the benchmark results show that Deltaformer outperforms the baseline.
b) 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% in FLOPs. However, in the code domain, the loss leads by 0.05. When training 300 B tokens, the code loss can match the baseline training at 400 B, which far exceeds the gain from FLOPs. We believe this is due to higher expressiveness.

Thank you very much for your constructive suggestions on our work. We hope the following response can solve your concerns.

1.The paper could be written with better style and clarity.

Thank you for pointing this out. We sincerely apologize for the unclear expressions that led to confusion. We have carefully revised the corresponding parts in the revised manuscript to better convey our intended ideas. We greatly appreciate your feedback, which helped us improve the clarity of our presentation.

2.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.

Thank you very much for your valuable suggestion. We compare it in our supplementary materials currently, and we will compare it in subsequent versions within the main text.

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 * n size matrix. The details can refer to the Readme file in the supplementary materials of the Triton implementation.

3.It was not made clear why "swap" is NC1 complete under AC0 reductions.

Thank you for your suggestion. Firstly, starting from literature [1], the permutation group over 5 elements is non-solvable, hence NC1-complete. Then permutations and several swaps can be converted to each other easily, for example, (a1 a2 a3 a4) (a5)=(a1 a2) (a1 a3) (a1 a4) (a5). Therefore, only considering the swap, it is still NC^1- complete. [1] Bounded-width polynomial-size branching programs recognize exactly those languages in nc. pp. 1–5, 1986.

4.Considering that you generalised the readout function, it would have made sense to ablate the $\kappa_2$ design on retrieval tasks too.

Thank you very much for your suggestion. We conducted corresponding experiments on MQAR[1]. The setting is vocab_size=256, input_seq_len=128,num_kv_pairs=32,d_model=32. And we controlled $\kappa_1$ to be linear to avoid that it enhence the ability of retrieve. The experimental results are as follows. We can find that the retrieval ability of linear is very poor.

[1] Zoology: Measuring and Improving Recall in Efficient Language Models

5.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.

We compared linear and nonlinear in Appendix B.1. It can be found that when the number of elements to be tracked exceeds the head dim, the linear method will have severe degradation. We must acknowledge that if our future tasks are not so difficult and the model only needs to track the movement of chess pieces on the board, then a linear kernel with head dim=128 is sufficient. But if we want to track the movement of tens of thousands of objects. Instead of using a linear kernel, it's better to try a non linear deltaformer.

6.The theorems and proofs could be better explained. It took me a disproportionate amount of time to parse.

Lemma1 of rwkv7 proves that the linear form of delta rule can achieve the ability to track element swapping, and it uses head dim $O (n)$ to complete its proof. Moreover, due to the finite state space that is displayed and easy to understand, the entire proof process is relatively simple.

And our Theorem 1 proves that even when we use the no-linear delta rule, we can still achieve the ability to track element swapping, and the required head dim changes from $O (n)$ to $O (log n)$. Due to nonlinearity, the state space cannot be written explicitly, making the entire proof process complex.

The key to proving the Theorem 1 is that there are quite a few almost orthogonal directions in n-dimensional space, and when we use nonlinear functions as a new similarity measure, these directions become orthogonal under the new measure. And the proof process adopts mathematical induction, mainly to prove that at each step, implicitly, the positions participating in the exchange are exchanged, while the positions not participating in the exchange remain unchanged.

3.**Clarification of Theorem 1 and Related Statements **

Theorem 1 (rephrased) Let the list be $L=[1,2,\dots,n]$.
Define the swap operation $G_{i,j}$ as

Thank you very much for recognizing our work in addressing motivation and conducting evaluations from synthesis tasks to language modeling. At the same time, you have also raised some concerns, and we hope that our following response can solve your concerns.

1.Missing Baselines and Comparisons

Regarding compute efficiency, the number of parameters can be perfectly aligned, but the flops will slightly increase. On the 340m scale model, approximately 5% of flops were added. Later, we conducted experiments on the 14b activated MOE model, where the number of kv was 1/4 of the number of q. As a result, the flops in the self-attention section increased by 25%, and in the entire MOE model, the flops increased by 3%. Some interesting large-scale experimental results are listed here:

a) Firstly, the benchmark results show that the deltaformer outperforms the baseline b) 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% in 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 higher expressiveness. By the way, we are still working hard on optimizing training efficiency. There is an implementation of chunk wise that we wrote using Triton in the attachment. Its speed is currently only 1/3 of flash attention at 8k training length. But it is 22 times faster than naive recurrent implementation. As for the decode stage, the computation logic of deltaformer and transformer is similar, and in the case of I/O bound, there is almost no increase in time overhead.

Comparisons with hybrid models: the simpler approach of mixing DeltaNet layers with Transformer layers.

We must acknowledge that this is a very good question, with both theoretical and practical significance!

1. Firstly, theoretically speaking, this simple mixing, or mixing using positional encoding like path, can only be proven to track the exchange of n objects using O (n) head dim, which is constrained by the linear delta rule And we can rigorously prove that using a nonlinear kernel function, we can use the head dim of O (log n) to track the exchange of n objects
2. In practice, a) we can prove the fact that when the number of objects to be tracked, n, exceeds the head dim, the performance of a simple hybrid architecture will significantly degrade in the synthetic data of the swap task, which is similar with the result in Appendix B.1 b) In small-scale language modeling tasks with 340m parameters, no significant differences can be seen. c) In larger scale tasks, more resources are needed for comparative experiments. We will verify it when we have sufficient computing resources in the future.
3. In the end, we argue that a formulation grounded in more principled foundations is more elegant than a simple hybrid.

And their purpose of mixing is to improve the insufficient retrieval ability of linear models. From this perspective, simple mixing models are successful. If it is to track the exchange of exponential objects, simple mixing is not effective. We must also acknowledge that if our future tasks are not so difficult and the model only needs to track the movement of chess pieces on the board, then a delta with head dim=128 is sufficient. But if we want to track the movement of tens of thousands of objects, so instead of using a linear deltaet, it's better to try a non linear deltaformer.

2.Figure 2 is potentially misleading.

You're absolutely right that being in a certain class doesn't necessarily mean it can solve all the problems of that class. This diagram wants to convey is that within a certain class, it means that it is not restricted by classes lower than this class, and it can solve some problems within this class. We will clarify this in the future to avoid misunderstanding.

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.

1.The synthesis task has benefits, but small-scale models do not have significant gains. We appreciate this important observation. We conjecture that the limited improvements seen in synthetic tasks at small scale stem from two factors: a) the bulk of the pre-training distribution is dominated by shallow, memorization-heavy patterns, and b) the model capacity is insufficient for acquiring the deeper computational primitives that our architecture is designed to exploit.

Therefore, 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:

An 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.

2.**The presentation is weak. **

We 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.

3.Where is the state space model?

Mamba2, 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.

4.Details about the swap tasks.

It 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.

5.About position embeddings. We 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. We 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.

6.Figure 6b.

Yes, it's a single layer. We will improve our presentation to make our paper clear.

7.Why/How does matrix inversion enhance expressivity?

Matrix inversion broadens the representational power of the model for two key reasons.

a.Complexity-theoretic relevance
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.

b.Algebraic reduction to matrix inversion
Connectivity queries can be encoded as reachability in the adjacency matrix A. The series

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.

1.Regarding other quadratic methods that perform well on state-tracking tasks.
We agree that certain quadratic alternatives can indeed achieve competitive results on these benchmarks.

A. 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.

B. 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.

C. 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:

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.

2.Additional experiments on formal-language tasks to further support our theory.

In 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. We 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.

3.Evaluation at larger scale

We 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:

An 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.

4.Clarifications requested by the reviewers

We thank the reviewers for their careful reading and for highlighting points that need further clarity. Below we address the questions. about 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.