Accelerating Toeplitz Neural Network with Constant-time Inference Complexity
Authors: Zhen Qin
Yiran Zhong
Venue: EMNLP 2023 Main (2023)
Keywords: Toeplitz Neural Network
inference
constant-time complexity
TL;DR: We preovide an algorithm that enables a closed-form, training free conversion from the Toeplitz representation to the SSM representation, ensuring numerical stability.

Abstract: Toeplitz Neural Networks (TNNs) have exhibited outstanding performance in various sequence modeling tasks. They outperform commonly used Transformer-based models while benefiting from log-linear space-time complexities. On the other hand, State Space Models (SSMs) achieve lower performance than TNNs in language modeling but offer the advantage of constant inference complexity. In this paper, we aim to combine the strengths of TNNs and SSMs by converting TNNs to SSMs during inference, thereby enabling TNNs to achieve the same constant inference complexities as SSMs.
To accomplish this, we formulate the conversion process as an optimization problem and provide a closed-form solution. We demonstrate how to transform the target equation into a Vandermonde linear system problem, which can be efficiently solved using the Discrete Fourier Transform (DFT).
Notably, our method requires no training and maintains numerical stability. It can be also applied to any LongConv-based model. To assess its effectiveness, we conduct extensive experiments on language modeling tasks across various settings. Additionally, we compare our method to other gradient-descent solutions, highlighting the superior numerical stability of our approach. The source code is available at https://github.com/OpenNLPLab/ETSC-Exact-Toeplitz-to-SSM-Conversion.

Toeplitz Neural Networks (TNNs) have exhib- ited outstanding performance in various se- quence modeling tasks. They outperform com- monly used Transformer-basee models while benefiting from log-linear space-time complex- ities. On the other hand, State Space Mod- els (SSMs) achieve lower performance than TNNs in language modeling but offer the ad- vantage of constant inference complexity. In this paper, we aim to combine the strengths Accelerating Toeplitz Neural Network with Constant-time Inference Complexity
Zhen Qin, Yiran Zhong
OpenNLPLab, Shanghai Artificial Intelligence Laboratory
Abstract
Zhang al., 2020; Gulati et al., 2020; Sun et al., 2022a), becoming one of the pest-performing ap- proaches across different benchmarks. The core component of the Transformer, the attention mecha- nism, has quadratic time complexity with respect to sequence length, making it challenging to scale to long sequences and large model sizes. Vari- ous methods have been proposed address this issue, including Linear Attention (Katharopoulos et al., 2020; Choromanski et al., 2020; Qin et al., 2022b, 2023b), State Space Model (SSM) (Gu et al., 2022: Gupta et al., 2022), Toeplitz Neural Network (TNN) (Qin et al., 2023a) and other Long- Conv methods (Li et al., 2023).
TNNs and SSMs by converting TNNs to SSMs during inference, thereby enabling TNNs to achieve the same constant inference com- plexities as SSMs. To accomplish this, we formulate the conversion process mization problem and provide a closed-form solution. We demonstrate how to transform the target equation into Vandermonde lin- ear system problem, which can efficiently solved using the Discrete Fourier Transform (DFT). Notably, our method requires no train- ing and maintains numerical stability. It can be also applied to any LongConv- based model. To assess its effectiveness, we conduct exten- sive experiments on language modeling tasks across various settings. Additionally, we com- pare our method to other gradient-descat solu- tions, highlighting the superior numerical sta- bility of our approach. The source code is avail- able at Exact- toeplitz-to-SSM-CCOn
opti-
Linear Attention reduces the space-time com- plexity of attention to linear by using kernel trick to decompose the Softmax function (Choromanski et al., 2020; Qin et al.. 2023c), but its poor per- formance (Qin et al., 2022a) prohibits it from be- ing used to build Large Language Models (LLMs). SSM replaces the attention operation with state space equations, resulting in log-linear training space-time complexities (Gu et al., 2022). How- ever, the performance this method in casual lan- guage modeling is often inferior (Qin et al., 2023a) and initialization-seeniivve (Gu et al., 2022), mak- ing it unsuitable for building LLMs.
PLab/EESCC
TNN a new class of sequence modeling meth- ods that belongs to LongConv-based methods (Li et al., 2023; Qin et al., 2023a). It models long se- quences using Toeplitz matrices to encode relative positional relationships. This key component al- lows them to effectively capture the dependencies within the sequence and make accurate predictions. has log-linear space-time time complexity and out- performs Transformers in NLP and long sequence modeling tasks (Qin et al., 2023a). Additionally, its stable training capability and insensitivity to initialization make it feasible for LLMs.
1 Introduction
Transformer has dominated the fields of computer vision (CV) (Dosovitskiy et al., 2020; Liu al., 2021; Sun al., 2022b), natural language process- ing (NLP) (Radford al., 2018: 8; Devlin et al., 2019; Radford et al., 2019; Brown et al., 2020; Liu et al., 2022), and speech processing (Karita et al., 2019;
X Indicates the corresponding author (Email address: @hongyiran cmm)..com)
Note that the above analysis has only taken into account the training complexities for the afore-

---

mentioned methods. However, when considering the deployment of LLMs, the inference complexi- ties are also important. In decoder scenarios, i.e., casual language modeling, the time complexity of inferring the 1hth token in the Transformer is On + nd)), where d are the sequence length and the feature dimension respectively. By using the KV cache technique (Pope et al., 2022), the complexity can be reduced to (nd?). For Linear Attention, the complexity is O(dh) (h is the hidden dimension), which makes constant with respect to the sequence length (Katharopoulos et al., 2020). SSM also has a constant space-time complexity of (dh),, where h is the hidden space dimension (Gu et al., 2022). TNN, on the other hand, has log- linear space-time complexity of (nd log n) in in- ference, which may make it challenging handle long sequences.
LongConv-based models.
2 Background and Preliminary
In this section, we first define sequence model in- ference mathematically and then briefly discuss the inference complexities of Transformer and some closely related efficient sequence modeling meth- ods such as Linear Transformer (Katharopoulos et al., 2020), SSM (Gu et al., 2022), and TNN (Qin et al., 2023a).
2.1 Inference
Inference refers to the process of predicting the next token given language model FF and a token sequence R". It can be represented follows:
logits = F(x) E RaxV
(1)
Fn 11 = Sample(logits(-1]]
In this paper, aim to accelerate the inference of TNN constant-time complexity. We find that SSM can be thought of as a particular variation of TNN. TNN can benefit from the same inference complexity as SSM if we can convert it to SSM in inference. We show that such conversion can be viewed as an optimization problem and can be ef- ficiently solved by closed-form solution. Specif- ically, given Toeplitz matrix, first convert it to Vandermoode Linear System with Inclusive Equation Reformulation (IER) and then employ the Discrete Fourier Transform (DFT) obtain a numerical stable result. Compared with gradient- based algorithms, our method is fast, training-free, and numerically stable. Note that our method can be applied to other LongConv-base methods (Li et al., 2023) as well.
where represents the size of the vocabulary, logits represents the output logits from the lan- guage model, and Fn+1 is the sampled token. The inference process continues until Ix+1 is the end- of-seuuence token (eos), indicating the completion of inference. The time and space complexity of inference is determined by the underlying language model F.
2.2 Inference Complexity
Transformer The Transformer's core component is self-attention, which operates on queries Q. keys K, and values V. Each component is a linear map- ping of the input X Raxd given by:
Q XWo. k= XWk. V XWv e Raxd
(2)
We conduct extensive experiments to validate the effectiveness of our method. We compare our method with gradient- based methods in terms of efficiency and errors. Our method outperformed gradient-based methods significantly in efficiency while enjoying much lower error rates. We also ap- ply our method to TNN language models and test in real scenarios. Our method has equivalent extrap- olation capabilities and perplexity to the original implementation of TNN. For the number of layers, sequence length, and feature dimensions, in- depth assessment of speed and memory utilization is performed. Our method clearly outperforms the original TNN inference algorithm implementation. Furthermore, we demonstrate the applicability of our strategy beyond TNN by extending it to other
The output of attention is computed as follows:
QQ T V.
Softmax
vR
Due to the need to compute QK T the time com- plexity of Transformer is Onn2d d + nd?). During the inference phase, when predicting the n-th to- ken, the naive time complexity is O + nd²), with space complexity of O(nd). By caching the previous time steps' K and V, known as KV cache, the complexity can be reduced to ((nd)).
Linear Transformer the Linear Transformer the Linear Attention, which uses the mapping ø(-) to map the Query and Key to their implicit representations, where
The core component of

---

(()) E Ruxh and h is the hidden dimen- sion. The output is then given by:
Toeplitz Neural Network and LongConv-based moethod The Toeplitz Neural Network (TNN) introduces token mixing (Yu et al., 2021) using a relative positional matrix or core computation can be expressed as follows:
0 A - (0 v].
(4)
Toeplitz matrix. The
A = diag( (f (Q))
By first computing ( V, the computational complexity can be reduced to (nddh). During the inference phase, according to (Katharopoulos et al.,
y =TTx, x.y x.EER.
(10)
where:
2020), we can transform the Linear Attention into the form of RNN:
ta
hn-1
ag = 0, by 0,
T
tt
E CR
(11)
& (kn) vil b, - á (kn).
t-1 to
R an-1
f--1
f1
(5)
O2 à (qn)
Using the Fast Fourier Transform (FFT), the ma- trix multiplication above can be computed in Ogg time complexity, which makes the TNN's time complexity log n). During the inference phase, according the Eq. 10, the com- plexity for predicting the nh token O(nd log n). Since TNN can be viewed as a form of LongConv- based methods (Li et al., 2023), other LongConv- based methods have the same complexities.
@ (q.) b..
This results in time and space complexity of (hdd) for the Linear Transformer.
State Space Model The State Space Model (SSM) (Gu et al., 2022) to use state space equa- tions for sequence modeling:
Ur Au..
Ban: Un = Cu,,
(6)
Method
where:
A A hxb BER "CER In, yn Un R
The inference of TNN exhibits a time complexity of OOnd and space complexity O(nd) for pre- dicting the n-th token which poses challenges for scaling TNN to handle extremely long sequences in inference. In this section, we will present our approach to converting TNN into the form of SSM, aiming to improve generation speed and memory to a constant.
(7)
Here, h represents the hidden dimension of the state space model. Note that we have swapped the positions of x; and compared to (Gu et al., 2022) for notational consistency. By expanding the Eq. 6, write the SSM as:
V/ Σ CA CAA-BB,,, 0. 0.... 7-0
(8)
3.1 Problem formulation
In this section, we show the connection between TNN and SSM and formulate our problem mathe- matically. Considering language modeling sce- nario, the token mixing process can be written as:
This allows for parallel training and has a plexity of O(nd log n). SSM has demonstrated its effectiveness many long sequence modeling tasks (Gu et al., 2022).
As variance of SSM. DSS (Gupta et al., 2022) suggests that assuming A to be a diagonal matrix A can mitigate the initialization sensitivity (Gu et al., 2022) while maintaining comparable model perfor- mance. In this case, the equation can be simplified follows:
Vi Σ 4-zzy J=0
i= i=....,,
(12)
On the other hand, SSM can be represented as:
B = Σ CA CA''B i= 1=0...,,
(13)
1=0
CA B
Σ cabiii
(9)
Let E. CA'B, B, the equation can be rewritten as:
During the inference phase, due to the Eq. 6, the computational complexity is O(hd).
3 =
Σ
h-say == O...., R-
(14)
0=0

---

Inclusive Equation
Discrete Fourier Transform
Reformulation
En
Vb
Toeplitz
Lo
Vandermonde Linear System
Up Au BXn Yn C2t
Representatinn
C2
F1
EO
Eg
22
Unroll The Recursion
Figure I: The conversion between Toeplitz. representation and SSM representation. Unrolling the recursion can tranform SSM representation Toeplitz representation. To obtain the inverse conversion, the Inclusive Equation Reformulation to express the problem as Vandermonde Linear System. Then, we apply the Discrete Fourier Transform (DFT) to compute the SSM representation.
Since DSS is as effective as SSM (Gupta et al., 2022), but DSS has simpler form, we choose DSS as our desired simplified structure. In this case, have:
The above issues make the gradient-based method less effective in achieving an accurate and efficient conversion from TNN to SSM. We adopt this al- baseline method and present it in Figure 2. The algorithm is summarized in Algo- rithm 2.
gorithm
CA'B Σ
(15)
3.3
Our closed-form solution
Notably, ob;; can be combined, so without loss of generality, we assume C = 1n:
In this section, we show that Eq. can be directly solved with a closed-form solution, i.e., find the exact values of A and by that result in the desired Toeplitz matrix representation. With the closed- form solution, we can avoid the issues associated with the gradient-based approach and achieve more accurate conversion from TNN SSM.
CA'B
Σ beA
(16)
By comparing the equations, is evident that SSM is a special case TNN. Since TNN inference encounters performance bottlenecks while SSM does not, the natural question arises; can we "con- vert" TNN to SSM in inference? This question is equivalent to find matrices A and B such that:
To do this, we first add a variable b to both sides the equation, yielding:
t: =
O....,
(19)
kmd
Mab. 0= n-1
(17)
Expanding this equation into matrix form, we have:
By determining suitable values for A and B, we can achieve an equivalent representation between TNN and SSM
to l
I
1
A
An
3.2
Gradient-based method
L
A
xn-1
Ln-
(20)
One solution to solve Eq. 17 is to use gradient- based methods to solve the following optimization problem:
t= Vb.
t R" V (b++1) b E (1(++))
Now, let's set h = n 1. we have:
h-
C
bt.ba
(18)
bo
R=0
Ag
An
bi
where C is the loss function, which can be & or &z.
(21)
However, this approach has two issues:
X
bb-
It cannot exactly satisfy Eq. 17, resulting in information loss during the conversion.
Vb.
t E RR" V E 1g
EER.
The presence of exponential terms A makes the optimization challenging to converge. (Gu
At this point, V is a Vandermonde matrix. Al- though the Vandermonde linear system is un-
et al., 2022)

---

stable in general due to numerical precision is- sues (Gautschi, 2020), if the Aς is are pairwise dis- tinct, the equation will have a solution. To improve stability, we can choose A = exp 2ime which results in V = V/W,n n. where Wn is the Discrete Fourier Transform (DFT) matrix. The above equa-
Algorithm 1 ETSC: Exact Toeplitz-to-SSM Con-
version
Input: E E..
Output: À E C" C C".
Notation: Use W& to represent the k-th order
DFT matrix.
tion can be expressed as:
Initialize:
1--1 ti]) E R"+1 t concat((t, 2i=0
== Wh, w Vob,
(22)
A exp( 2T 11/m + 1),5 0, ,,..., 1,
Efft W Wn+t Pa+1
where W represents the conjugate transpose of the matrix W. By comparing the first row, have:
b O₂, E IR.".
for in O...., n - 1 do:
b: tan (i + 11/ n vll/v++1
Σ =0 O.
(23)
end for
However, the coefficients from TNN are guar- anteed to satisfy this equation. To ensure that this equation is satisfied, we introduce another variable fn Σi= t, which we call an inclusive equa- tion reformulation process. Therefore, we have:
Algorithm 2 Gradient-Bard Based Method
Input: t E RR:
Output: À E C, C";
Initialize:
O, breat, Bing (O,Inn) Minimize:
1
Xa
An-1
bi
h-1
bn-1
(24)
Σ
Nobs
tx
bn- 2
A=0
IW Ibb,, R ((++))+++))
where
1 LE LER""l.ve
R
(r)
Based on the above equation, we can determine the coefficients by using the expression:
b breal + i ibing.
1 [+]
(25)
Vn
Origin In the inference phase, our core operation remains the computation of T'x'. One approach for inference is to continue using the Fast Fourier Transform (FFT), which results in a time complex- ity of Ondllogn)
By utilizing this formula, we can obtain the coef- ficients 4, We name this method as ETSC (Exact Toeplitz-to-SM Conversion) and provide sum- mary of the algorithm in Algorithm 1.
3.4 The inference of TNN
This method is to directly compute Eq. 12, which requires matrix multiplication and has a time complexity of O(n'd + ndf). However, by employing a caching mechanism similar to the key-value (KV) cache in transformer (Pope et al., 2022), we can store the output of each layer as cache' = x++ E gaxd, In this way, when per- forming a new inference, we only need to compute:
Cache
In this section, we briefly introduce three inference strategies of language modeling for TNN: the Orig- inal implementation, i.e., FFT. Cache and SSM. In the subsequent discussion, let us assume we have an L-layer TNN with the superscript (I) indicating the result at the I-th layer. The computation of TNN can be represented as follows:
x (mboddinggi) E gaxd
(27)
++| -'xx' gnxdd 1= O,..,, L-1 (26)
Logits w R2eV
Then, we update as follows:
cache' concat (ccache, on ++11),
Here, i E R represents the input tokens and V represents the vocabulary size.
(28)
I .+11 cache'.

---

Table 1: Extrapolation Evaluation on TNN. We trained a TNN LM and, upon completion training, utilized ETSC to convert the coefficients of the Toeplitz matrix into SSM representation. We then evaluated the model's extrapolation capability, comparing the results for different hidden states. It can be observed that our model exhibits extrapolation abilities similar to TNN. Moreover, for hidden states of 768 and 1024, ETSC achieves average perplexity (ppl) comparable to TNN.
Seqlen
Dataset
512
1024
2048
4096
8192
9216
10240
12288
14336
AVG
TNN
24.67
24.05
23.73
23.58
23.51
23.49
23.48
23.48
23.46
23.72
wikitxt-
512
24.65
24.47
24.37
24.32
24.29
24.29
24.28
24.28
24.28
24.36
103
768
24.65
24.04
23.74
23.59
23.52
23.51
23.49
23.49
23.48
23.72
1024
24.65
24.03
23.72
23.57
23.50
23.49
23.47
23.47
23.46
23.71
TNN
23.87
23.28
23.00
22.80
22.73
22.70
22.69
22.55
22.62
22.92
wiki- book
512
23.87
23.28
23.00
22.80
22.73
22.70
22.69
22.55
22.62
22.91
768
23.87
23.30
23.04
22.85
22.78
22.75
22.74
22.55
22.67
22.95
1024
23.87
23.28
23.00
22.80
22.74
22.70
22.69
22.56
22.62
22.92
Table 2: Evaluation of ETSC Other LongConv Methods. We conducted experiments to the performance of ETSC on other LongConv methods, specifically focusing SGConv. We trained an SGConv LM and applied ETSC to convert the Toeplitz representation into SSM representation. We then evaluated the extrapolation capabilities of the converted model. This demonstrates that ETSC exhibits extrapolation abilities similar SGConv, with even lower average perplexity (ppl) values.
Seglen 512
1024
2048
4096
8192
9216
10240
12288
14336
AVG
SGConv
33.39
32.77
32.46
32.31
32.24
33.61
33.59
32.22
34.54
33.01
33.39
32.77
32.46
32.31
32.24
32.24
32.22
32.22
32.20
32.45
With this approach, the time complexity can be reduced to O(nd)).
to 64 and vary the sequence length from 64 to 8192.
Our method is 3 to 6 orders of magnitude faster than the gradient-based method. Regarding the relative error, our method achieves an error close to zero, while the relative error of gradient-based methods exceeds 30%.
SSM With our method, we can transform the Toeplitz representation into a State Space Model (SSM) representation. Therefore, we can perform inference using Eq. 6, resulting in both time and space complexities of O(hd).
We then fix the sequence length to 2048 and vary the feature dimension from 64 to 16384. The gradient-based methods encounter OOM at d = 512 while our method successfully completes all tests. Our method is 4 orders of magnitude faster. In terms of relative error, our method achieves ror close zero, while the relative error of gradient- based methods is around 35%.
4 Experiments
In this section, we present extensive experiments validate our method. We first analyze the nu- merical stability and efficiency of our method with a comparison to a gradient-based approach. Then we evaluate our method for language modeling tasks with real-world scenarios. In our inference efficiency study, we conduct an in-depth analysis of the impact of the number of layers, sequence length, and feature dimensions the speed and memory utilization of our method. We also extend the scope of our method to other long convolution- based methods, showcasing its versatility and gen- eralizability.
Our method demonstrates superior numerical sta- bility and efficiency compared to gradient-based methods. It significantly reduces the computation time while maintaining a low relative error. Fur- thermore, our method exhibits excellent scalability, as it can handle larger sequence lengths and higher feature dimensions without encountering OOM.
4.2 Evaluation on TNN LM
Following the configuration used in (Qin et al., 2023a), trained 6-layer TNN LM the Wikitext-103 and Wiki-book (Wettig et al., 2023) dataset with a feature dimension of 512, maximum sequence length of 512, and 50k update steps. Af- ter training, we utilize ETSC to convert the coeffi-
4.1 Numerical Stability and Efficiency
Figure presents the comparison in terms of time complexity and relative error ||t-l where [|
t to, ... ...,..., tx- represents the coefficients of the Toeplitz matrix. We first fix the feature dimension

---

15
Gradient Based
Ours
101
107
Relaivv Entr
Thrre Cost
107
137
107
10
40a
10
404
1020
2020
3000
1000
3003
5030
7000
B303
1000
2000
3000
4000
5000
6000
7002
8000
Sequence Longth
Sequence Length
(a) Sequence Length
Time Cost
(b) Sequence Length v.S. Relative Error
105
Gradient Besed + Ours
10
Time Oost
107
337
107
15
10A
10
10a
Festure Dimension
Feature Dimersion
(c) Feature Dimension v.s. Time Cost
(d) Feature Dimension v.S. Relative Error
Figure 2: Comparison of ETSC and Sradient-Based Methods. We compare the time overhead and relative error |t tmed ETSC and gradient-based methods, where the unit of time overhead is seconds and the unit of relative
[b]]
error is percent. Here, = [to..... 4n- represents the coefficients of the Toeplitz matrix. can observed that ETSC exhibits significantly lower time overhead compared to gradient-based methods, while also achieving smaller errors.
cients of the Toeplitz matrix to SSM and vary the sequence length from 512 to 14336 to verify the model's extrapolation capabilities. We test with three hidden state dimensions: 512, 768, and 1024.
and Cache methods in terms of their practical in- ference time and memory usage. All methods are evaluated the same A100 GPU. Specifically, we select a TNN LM and vary the sequence length, feature dimension, and number of layers to assess the effectiveness of the methods.
Table shows the results of our evaluation. It can be observed that ETSC exhibits the same ex- trapolation capabilities TNN, enabling it to han- dle sequences of arbitrary length. Moreover, when the hidden state dimensions are larger than 512, ETSC achieves comparable average perplexity to TNN, demonstrating ETSC preserves model- ing capacity of TNN while providing the benefits of numerical stability and efficiency.
In the sequence length test, we fix the number of layers at and the feature dimension at 64. In the feature dimension test, we fix the number of layers at 2 and the sequence length at 2048. In the layer test, fix the sequence length at 2048 and the fea- ture dimension at 64. Figure (a) and (b) illustrate the results of the sequence length test. It can be ob- served that the Origin and Cache methods exhibit significantly higher inference times and memory utilization, ranging from several times to tens of times longer than ETSC. Additionally. the memory utilization of Origin and Cache is almost 2 orders of magnitude higher when the sequence length ex- ceeds kk. In the feature dimension test, as shown in Figure 3 (c) (d), both the Origin and Cache meth- ods exhibit inference times several times to tens of times longer than ETSC, with memory utiliza- tion approximately 100 times higher. The layer test
Our evaluation the TNN LM demonstrates that ETSC not only possesses extrapolation capa- bilities but also achieves comparable performance to TNN in terms of average perplexity. This fur- ther confirms the effectiveness and practicality of ETSC in long sequence modeling tasks.
4.3 Inference Efficiency Analysis
this section, we discuss the impact of hyper- parameters on inference time and memory utiliza- tion. We compare ETSC with the Origin (FFT)

---

Origin Cadhe
Origin Cache
Ours
Relative Memory Cast
Realive Cost
100
10
Sequeriee Length
Sequence Lengih
(a) Sequence Length V.S. Relative Time Cost
(b) Sequence Length V.S. Relative Memory Cost
10
Origin
Ours
Origin
Cache
Reluiive Mermory Cost
Reaabe Cost
1o7
-00
10
107
1000
Feature Dimersion
Fealure Dimension
(c) Feature Dimension Relative Time Cost
(d) Feature Dimension V.S. Relative Memory Cost
101
10
Origin
Ours
Origin
Ours
Cache
Cache
Relatie Memory Cost
Relalive Time Cost
Number Of Layers
Numbar Cf Layers
(c) Number Layers v.s. Relative Time Cost
(f) Number Of Layers v.s. Relative Memory Cost
Figure Impact Hyperparameters on Inference Time and Memory. compared the actual inference time and memory usage of ETSC, Origin (FFT), and Cache methods under different sequence lengths, feature dimensions, and model depths. Our method consistently outperformed the other methods, significantly reducing both the inference time and memory usage all scenarios.
results shown in Figure 3 (e) (f). The Origin and Cache methods again exhibit inference times several times to tens of times longer than ETSC, with memory utilization approximately 100 times higher or more.
this claim, selected SGConv (Li et al., 2023) and trained an SGConv language model. After training, we used ETSC to convert the Toeplitz representa- tion to the SSM representation. We then varied the sequence length in the range from 512 to 14336 to evaluate the model's 's extrapolation capabilities. From Table 2, it can be observed that ETSC exhibits the same extrapolation capabilities as SG- Conv and achieves lower average perplexities. This indicates that method be effectively ap- plied other LongConv methods as well, further demonstrating versatility and effectiveness long sequence modeling tasks.
These results demonstrate the superior efficiency of ETSC compared to the Origin and Cache meth- ods across different configurations. ETSC consis- tently outperforms the other methods in terms of both inference time and memory utilization. This highlights the advantage of ETSC for efficient and scalable inference in long sequence modeling.
4.4 Application to Other LongConv-based Methods
5 Conclusion
Our method is applicable to all LongConv methods, as they all rely on Toeplitz matrices. To validate
In this paper, we have analyzed and addressed the efficiency issue in TNN inference. We propose

---

solution by converting the Toeplitz representa- tion the SSM representation, which reduces the time and space complexity of TNN inference to be independent of the sequence length. Our con- version algorithm, named ETSC, is fast, training- free, and numerically stable, outperforming other gradient-basee methods significantly while keeping the same extrapolation capabilities and perplexity the original TNN. We conducted comprehen- sive assessment of the performance of our method in terms of the number of layers, sequence length, and feature dimensions. Our results clearly demon- strate that our method surpasses the original TNN in terms of both speed and memory utilization. Additionally, we extended the applicability of our strategy beyond TNN by successfully applying it to other LongConv- based models, showcasing the versatility and effectiveness of our approach.
domains and model architectures.
While our proposed method offers a compelling approach for converting Toeplitz representations to State Space Models, it is important to consider the limitations mentioned above. Addressing these lim- itations and further exploring the potential of our method in diverse domains and model architectures will be valuable directions for future research.
References
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan. Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin. Scott Gray, Benjamin Chess, Jack Clark, Christopher Bemnrr, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language models are few-shot learners. arXiv.
Acknowledgement
This work is partially supported by the National Key R&D Program of China (NO.2022ZI0160100))
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sar- los, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, al. 2020. Rethinking attention with performers. arXiv preprint MeXXiv:2009,179990
Limitations
While our proposed method for converting Toeplitz representations to State Space Models (SSM) has shown promising results in our experiments, there are certain limitations that should be acknowl- edged.
Jacob Devlin, Ming- Wei Chang, Kenton Lec, and Kristina Toutanova. 2019, Bert: Pre-training of deep bidirectional transformers for language understand- ing. Proceedings of the 2019 Conference of the North American Chapter of the Association for Com- putational Linguistics: Human Language Technolo- gies, Volume (Long and Short Papers), pages 4171- 4186.
Trade-off between Accuracy and Efficiency: Although our method achieves significant improve- ments in efficiency, it important to note that there may be a trade-off between accuracy and efficiency. The conversion from Toeplitz. representations to SSM involves approximations and simplifications, which can introduce some level of error compared to the original representation. While our experi- ments have demonstrated comparable performance the original Toeplitz Neural Network (TNN), there may be scenarios where the transformed SSM does not fully capture the intricate patterns present in the original model.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn. Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. 2020. An image is worth 16x words: Transformers for image recognition scale. In International Conference on Learning Representations.
Walter Gautschi. 2020. How (un) stable are vander- monde systems? In Asymptotic and computational analysis, pages 193-210. CRC Press.
Albert Gu, Karan Goel, and Christopher Re. 2022. Ef- ficiently modeling long sequences with structured state spaces. In International Conference Learn- ing Representations.
2. Application Scope: Our method has been extensively evaluated in language modeling tasks and demonstrated superior performance compared gradient-based methods and the original TNN implementation. However, the applicability of our method may be limited to sequence modeling tasks and long convolution basedd models. Further re- search is needed to explore its effectiveness in other
Anmol Gulati, James Qin, Chung-Cheng Chiu, Niki Parmar, Yu Zhang, Jiahui Yu, Wei Han, Shibo Wang. Zhengdong Zhang, Yonghui Wu, and Ruoming Pang- 2020. Conformer: Convolution-augmenned Trans- former Speech Recognition. In Proc. Interspeech 2020, pages 5036-5040.

---

Ankit Gupta, Albert Gu, and Jonathan Berant. 2022. Diagonal state spaces are as effective as structured state spaces.
Zhen Qin, Weixuan Sun, Kaiyue Lu, Hui Deng, Dongxu Li, Xiaodong Han, Yuchao Dai, Lingpeng Kong, and Yiran Zhong. 2023c. Linearized relative positional encoding. Transactions on Machine Learning Re- search.
Shigeki Karita, Nelson Enrique Yalta Soplin, Shinji Watanabe, Mare Delcroix, Atsunori Ogawa, and To- mohiro Nakatani. 2019. Improving Transformer- Based End-to-End Speech Recognition with Connec- tionist Temporal Classification and Language Model Integration. In Proc. Interspeech 2019, pages 1408- 1412.
Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya Sutskever. 2018. Improving language under- standing by generative pre-training.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, llya Sutskever, et al. 2019. Language models are unsupervised multitask learners. OpenAl blog, 18)):
Angelos Katharopoulos, Apoory Vyas, Nikolaos Pap- pas, and François Fleuret. 2020. Transformers are mns: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning, pages 5156-5166 PMLR.
Jingyu Sun, Guiping Zhong. Dinghao Zhou, Baoxiang Li, and Yiran Zhong. 2022a. Locality matters: A locality- biased linear attention for automatic speech recognition. arXiv preprint arXiv:2203. 15609.
Yuhong Li, Tianle Cai, Yi Zhang, Deming Chen, and Dehadeepta Dey. 2023. What makes convolutional models great on long sequence modeling? In The Eleventh International Conference on Learning Rep- resentations.
Weixuan Sun, Zhen Qin, Hui Deng. Jianyuan Wang. Yi Zhang, Kaihao Zhang. Nick Barnes, Stan Birchfield, Lingpeng Kong, and Yiran Zhong. 2022b. Vicinity vision transformer. arXiv preprint arXiv:2206. 10552.
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. 2021. Swin transformer: Hierarchical vision trans- former using shifted windows. arXiv preprint 1031v:2103.14030.
Alexander Wettig, Tianyu Gao, Zexuan Zhong, and Danqi Chen. 2023. Should you mask 15% in masked language modeling? In Proceedings of the 17th Conference of the European Chapter of the Asso- ciation for Computational Linguisties, pages 2985- 3000, Dubrovnik, Croatia, Association for Computa- tional Linguistics.
Zexiang Liu, Dong Li, Kaiyue Lu, Zhen Qin, Weixuan Sun, Jiacheng Xu, and Yiran Zhong. 2022. Neu- ral architecture search efficient transformers and beyond. arXiv preprint 2rXiv:2207.13955
Weihao Yu, Mi Luo, Pan Zhou, Chenyang Si, Yichen Zhou, Xinehao Wang, Jiashi Feng, and Shuicheng Yan. 2021, Metaformer actually what you need for vision.
Reiner Pope. Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Anselm Levskaya, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. 2022. Efficiently scaling transformer in- ference.
Qian Zhang, Han Lu, Hasim Sak, Anshuman Tripathi, Erik McDermott, Stephen Koo, and Shankar Kumar, 2020. Transformer transducer. A streamable speech recognition model with transformer encoders and mn-t loss. In ICASSP 2020-2020 IEFF International Conference on Acoustics, Speech and Signal Process- ing (ICASSP), pages 7829-7833. IEFE.
Zhen Qin, Xiaodong Han, Weixuan Sun, Bowen He, Dong Li, Dongxu Li, Yuchao Dai, Lingpeng Kong, and Yiran Zhong. 2023a. Toeplitz neural network for sequence modeling. In The Eleventh International Conference on Learning Representations.
Zhen Qin, Xiaodong Han, Weixuan Sun, Dongxu Li, Lingpeng Kong. Nick Barnes, and Yiran Zhong. 2022a. The devil linear transformer. Proceed- ings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 7025-7041, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
Zhen Qin, Dong Li, Weigao Sun, Weixuan Sun, Xuyang Shen, Xiaodong Han, Yunshen Wei, Baohong Lv. Fei Yuan, Xiao Luo. Yu Qiao, and Yiran Zhong. 2023b. Scaling transnormer to 175 billion parameters.
Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yun- shen Wei, Baohong Lv, Junjie Yan, Lingpeng Kong, and Yiran Zhong. 2022b. cosformer: Rethinking softmax in attention. International Conference on Learning Representations.


Reviews:
[{"review_id": "s6u6zVFIwn", "reviewer": "Reviewer_ehMV", "summary": "", "questions": "1. Can this method be integrated with other efficiency techniques to further enhance inference speed? If possible, which specific techniques might be suitable?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The paper is well-organized and easy to follow, and the author offers a comprehensive background context.\n2. The findings have the potential to significantly impact the LLM field or related domains, providing valuable insights for other researchers.", "reasons_to_reject": "1. Transitioning from Toeplitz representations to SSM requires certain approximations and simplifications. These adjustments can potentially introduce discrepancies compared to the original representation. \n2. The proposed methods have been assessed solely on language modeling tasks. It would be better to evaluate the model on more intricate tasks to fully evaluate the potential of this technique.", "questions_to_authors": "1. Can this method be integrated with other efficiency techniques to further enhance inference speed? If possible, which specific techniques might be suitable?", "paper_topic_and_main_contributions": "In the paper, the authors explore the potential of Toeplitz Neural Networks (TNNs) and their superior performance in sequence modeling compared to the prevalent Transformer-based models, emphasizing their log-linear space-time complexities. While State Space Models (SSMs) have a consistent inference complexity, they underperform TNNs in language modeling tasks. This research ambitiously merges the strengths of both TNNs and SSMs, converting TNNs into SSMs during inference. Experimental results underscore its effectiveness and numerical stability.", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gdLcCS9ljd", "reviewer": "Reviewer_78gu", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- Interesting results\n\n- Reducing inference-time complexity while allowing long sequences is a major research problem", "reasons_to_reject": "- Quite complicated method, no code, replication will be difficult\n\n- Evaluation is limited to a single dataset.", "questions_to_authors": "", "paper_topic_and_main_contributions": "The paper presents a method for efficient long-context sequence modelling with decoder-only transformers. Specifically, the paper combines the benefits of Toeplitz Neural Networks (TNNs), which enable good quality but suffer from log-linear (over the sequence length) per-token inference complexity with State Space Models (SSMs), which operate like RNNs at inference time, enabling constant-time per token inference complexity, but tend to underperform vanilla transformers in terms of quality.\n\nIn the proposed approach, a TNN is trained first, then it is converted to a SSM. Two conversion methods are evaluated: a simple gradient-based optimization method and a closed-form method.\n\nThe approach is evaluated on a single LM dataset (Wikitext-103), with the proposed method having similar perplexity to a TNN baseline. Various ablations and hyperparameter sensitivity results, and computational costs results are reported.\n\nThe authors also briefly mention extensions to other kind of \"LongConv\" approaches.\n\n-------------------\n\nConsidering the author's response, I have increased the soundness and reproducibility scores", "excitement": 3, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9qHUKr0fPC", "reviewer": "Reviewer_SKym", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The paper addresses an important and practical problem of improving the efficiency and scalability of TNNs and other LongConv-based models for long sequence modeling.\n2. The paper presents a novel and elegant solution that leverages the mathematical properties of Toeplitz matrices and SSMs, and provides a rigorous analysis of its correctness and stability.\n3. The paper conducts extensive experiments to validate the proposed method on language modeling tasks with different sequence lengths, feature dimensions, and model architectures. The paper also compares the proposed method with other gradient-based methods, highlighting its superior numerical stability and efficiency.", "reasons_to_reject": "1.  The proposed method may be viewed as a straightforward combination of existing techniques. The paper proposes to accelerate TNNs by converting them to SSMs during inference, which leverages the mathematical properties of Toeplitz matrices and SSMs. However, both TNNs and SSMs are well-established methods in the literature, and the conversion process may be seen as a simple application of known results. The paper may not provide enough novelty or insight beyond combining these two existing methods, and may not sufficiently justify the significance or impact of the proposed method. This could be a potential weakness of the paper that may limit its contribution to the NLP community.\n2. The paper may not sufficiently discuss the limitations and trade-offs of the proposed method, such as the potential loss of accuracy or expressiveness due to the conversion from TNNs to SSMs, or the applicability of the method to other domains or tasks beyond language modeling.", "questions_to_authors": "", "paper_topic_and_main_contributions": "This paper is about accelerating TNNs with constant-time inference complexity. TNNs are a class of sequence modeling methods that use Toeplitz matrices to encode relative positional relationships They have shown outstanding performance in various NLP tasks, but they suffer from log-linear inference complexity, which limits their scalability to long sequences. The paper proposes a method to convert TNNs to SSMs during inference, which reduces the inference complexity to constant. The paper formulates the conversion process as an optimization problem and provides a closed-form solution using the DFT. The paper demonstrates the effectiveness of the proposed method on language modeling tasks across various settings. The paper also shows that the method can be applied to other LongConv-based models, such as SGConv.", "excitement": 3, "reproducibility": 2, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to combine SSM and TNN to reach a better tradeoff between task performance and speed performance. Reviewers found this paper interesting, novel, and well-organized, and may benefit the research of other types of language models. Several concerns were raised initially regarding the limited results, low reproducibility, and insufficient analysis. The authors addressed them during the rebuttal periods, which are acknowledged by all reviewers. Therefore, the AC deemed this paper should be accepted for the main conference.
Decision: Accept-Main