ChordMixer: A Scalable Neural Attention Model for Sequences with Different Length
Authors: Ruslan Khalitov
Tong Yu
Lei Cheng
Zhirong Yang
Venue: ICLR 2023 poster (2023)
Keywords: Mixer
Attention
Scalable

Abstract: Sequential data naturally have different lengths in many domains, with some very long sequences. As an important modeling tool, neural attention should capture long-range interaction in such sequences. However, most existing neural attention models admit only short sequences, or they have to employ chunking or padding to enforce a constant input length. Here we propose a simple neural network building block called ChordMixer which can model the attention for long sequences with variable lengths. Each ChordMixer block consists of a position-wise rotation layer without learnable parameters and an element-wise MLP layer. Repeatedly applying such blocks forms an effective network backbone that mixes the input signals towards the learning targets. We have tested ChordMixer on the synthetic adding problem, long document classification, and DNA sequence-based taxonomy classification. The experiment results show that our method substantially outperforms other neural attention models.

Published as a conference paper at ICLR 2023
CHORDMIXER: A SCALABLE NEURAL ATTENTION MODEL FOR SEQUENCES WITH DIFFERENT LENGTHS
Ruslan Khalitov, Tong Yu, Lei Cheng & Zhirong Yang
Department of Computer Science
Norwegian University of Science and Technology
(ruslan, khalitov, tong . yu, lei. cheng, maironn.yyage @ntnu.no
ABSTRACT
Sequential data naturally have different lengths in many domains, with some very long sequences. As an important modeling tool, neural attention should capture long-range interaction in such sequences. However, most existing neural attention models admit only short sequences, or they have to employ chunking or padding to enforce a constant input length. Here we propose simple neural network building block called ChordMixer which can model the attention for long sequences with variable lengths. Each ChordMixer block consists of a position- wise rotation layer without learnable parameters and an flement-wise MLP layer. Repeatedly applying such blocks forms an effective network backbone that mixes the input signals towards the learning targets. We have tested ChordMixer the synthetic adding problem, long document classification, and DNA sequence-basee taxonomy classification. The experiment results show that our method substantially outperforms other neural attention models
INTRODUCTION
Sequential data appear widely in data science. In many domains, the sequences have a diverse distribution of lengths. For example, text information be short characters or as long as a novel with over 500,000 words] In biology, the median human gene length about 24,000 base pairs (Fuchs al.) 2014), while the shortest is 76 (Sharp et al. 1985) and the longest is at least 2,300,000 (Tennyson et al. 1995). Meanwhile, long-range interactions between DNA elements are common and can be up to 20,000 bases away (Gasperini al. 2020). Modeling interactions in such sequences is fundamental problem in machine learning and brings great challenges to attention approaches based on deep neural networks.
SMS limited to 160
Most existing neural attention methods cannot handle long sequences with different lengths. For efficient batch processing, architectures such as Transformer and its variants have been proposed, they usually assume constant input length. Otherwise, they have to use chunking, resampling, or padding to enforce the same input length. However, these enforcing approaches either lose much information cause substantial waste storage and computation. Even though some architectures, such as scaled dot-product (Vaswani et al. (0017). can deal with short sequences with variable lengths, they are not scalable to very long sequences.
In this paper, we propose novel neural attention model called ChordMixer to overcome the above drawbacks. The neural network takes sequence of any length input and outputs tensor of the same size. Moreover, ChordMixer scalable to very long sequences (we demonstrate lengths up 1.5M in our experiments).
ChordMixer comprises several modules or blocks with simple and identical architecture. Fach block has Multi-Layer Perceptron (MIP) layer over the sequence channels and multi-scale rotation layer over the element positions. The rotation has no learnable parameters, and therefore the model size of each block is independent of sequence length. After log, N ChordMixer blocks, every number the output has full receptive field of all input numbers for length N.
"oode is publicly available at http:////tthhiioo/////aaaaaathaa https:: http///wwwwikkekee wiki www.iieeia...g////..... http::////e...iiipaaa...ooo///// ott.pp/pppa.ooooo..../////taatap otgp:////ooocoooooooooooooooooon

---

Published as a conference paper at ICLR 2023
We compared ChordMixer with Transformer and many of its variants in three tasks sequential data: synthetic adding problem, long document classification, and DNA sequence- taxonomy classification. Our method wins in nearly all tasks, which indicates that ChordMixer mixes well the signals in long sequences with variable lengths and can serve as a transformation backbone place of conventional neural attention models.
The next section will briefly review the definitions and related work. We present the ChordMixer, including its design, properties, and implementation details, in Section 3 Settings and results of three groups of experiments are provided in Section In Section 3] we conclude the paper and discuss future work.
2 BACKGROUND AND RELATED WORK
sequential data instance, or a sequence, is a one-dimensional array of sequence elements or tokens. In this work, tokens are represented by vectors of the same dimensionality. Therefore a sequence can be treated as a matrix x E IR where is the sequence length and d is the token dimensionality (or the number of channels). Each sequence may have different length in data set, and the distribution N can have a high range.
Neural attention or mixing is basic function of neural network, which transforms data tensor into another tensor toward the learning targets. In the self-attention setting, the input and output tensors usually have the same size. Without losing information, neural attention should have full receptive field; that is, each output number can receive information from all input numbers. However, naively connecting each pair of input and output numbers is infeasible. Self-attention of sequence æ with the naive implementation requires 2 connections, which is too expensive when N is large.
Most existing neural attention methods employ two-stage mixing relieve the expense due to the full connections. For example, the widely used Transformer model (Vaswani et al.) (017)) alternates the token-wise and position-wis mixing steps. The connections are limited in each step, the receptive field becomes full after one alternation. However, Transformer has quadratic cost to sequence length because it fully connects every token pair.
Numerous approximation methods of Transformer have been proposed to reduce the quadratic cost. For example, Longformer (Beltagy et al. 2020) and ETC (Ainslie et al. 2020) use a learnable side memory module that can access multiple tokens at once; Nyströmformer (Xiong et al. (02T)) uses few landmarks as surrogates to the massive tokens; downsampling methods also include Perceiver (Jacgle al. (20TT) and Swin Transformer (Liu et al. 2021 2022); Performer (Choromanski et al.) 2020) and Random Feature Attention (Peng et al. [021] approximate the softmax kernel by low-rank matrix products; Switch Transformer (Fedus et al., 2021) and Big Bird (Zaheer et al.. 2020) use sparse dot-products at multiple layers. A more thorough survey can be found in Tay el al. (2022). However, the approximation methods still follow the scaled dot-product approach in the original Transformer, and thus their performance remains mediocre or inferior (Gu et al. 2022 Khalitov el al.
2022
Yu et 2022a).
3 CHORDMIXER
In this work, we go beyond the scaled dot-product approach and aim to develop a neural attention model with the following properties:
full-receptive field: every output number is mixed directly or indirectly from all input numbers of a sequence;
scalability: the new method can give accurate predictions for very long sequences;
decentrality: the new design is decentralized, where no sequence element position is more central or closer to the output;
length flexibility: the model can handle sequences of diverse lengths without extra prepro- cessing such chunking, resampling, padding.
2

---

Published as a conference paper at ICLR 2023
Moreover, do not assume that useful patterns appear only locally, and try to learn all possible interactions from data. Therefore we avoid operations such as pooling over local windows of the sequences.
3.1 INSPIRATION FROM P2P NETWORK
We find an analogous solution in the Peer-to-Peect (P2P) communication network to achieve the above properties (Stoica et al. 2001). Full-connection is a naive communication protocol when every peer tries to communicate with the other N peers. However, the naive protocol leads to huge routing tables, and message flooding often causes wasteful communication.
As solution, one of the best-known protocols in P2P is Chord, where all peers are organized in circle. At each hop of lookup, the i-th peer will communicate with the neighbors + ........ i + 2 at multiple scales and with modulus N, where information collected from the communication will be stored and communicated at the next hop. In the distributed setting, each peer is able collect information (directly indirectly) from all other peers after (logg .) hops (Stoica et al. 2001).
[log2 N1. See Figure (a) for illustration. The
3.2 CHORDMIXER BUILDING BLOCK AND NETWORK ARCHITECTURE
We mimic the P2P Chord protocol with artificial neural network by treating sequence tokens as peers, network blocks as hops, and transformations between blocks as communications. We called the resulting building block ChordMixer.
We divide the sequence rows or channels into M = [log, N + 1 tracks, where each track has about d/ M channels. Then each ChordMixer block contains two layers for an input sequence x." e RdxNN
1. (Rotate): the layer rotates the tracks at different scales (z E gdxN);
for i 1....,dd d.....dana and = 1,...,M, NN where
k = { (j ( mod N if >
if =
(2)
with 4 the track index of the i-th channel (starting from 1). Here we add the self-loop (a non-rotated track) the Chord protocol include the same token in mixing. The Rotate forward pass is illustrated in Figure (b)-(d).
The Rotate layer is cheap to implement. The copy operations from x to can run in parallel over i,J, k. and thus can efficiently be implemented by e.g., CUDA. It can also be done in PyTorch with the roll function. The backward pass is simply reverse rotation: aJ /rr.h = ÖJ /dzy for a learning objective J.
2. (Mix): transforms every token (column) with neural network f
out Fig
for j = 1....., N, where w is the network weights of f. In the experiments, we simply used two-layer MLP to implement with hidden dimension and GELU nonlinearity. We also apply dropout between the Rotate and Mix steps.
ChordMixer network consists of [logz Nmax] ChordMixer blocks, where Nuax the length of the longest sequence or the longest range of possible interactions. Each block has an identical architecture (with [log, N Nmax tracks) but a different f network. Residual connection is applied around each ChordMixer block.
ChordMixer network forms a backbone of a neural learner. We believe after the mixing, elements at every position summarize good information from all input positions. We can then use lightweight predictor (e.g., classifier or regressor) on the individual output tokens and integrate their predictions by ensemble learning. In this work, linear operation and averaging are exchangcable, we can first take the mean of output tokens and then apply the linear predictor.
linear predictors and ensemble averaging. Because the
3

---

Published as a conference paper at ICLR 2023
14
15
14
15
13
13
14
13
12
12
12
12
12
11
10
8
10
30
8
(c)
2
6
10
13
14
3
10
11
12
13
1
2
5
6
9
10
11
12
13
14
15
2
5
6
8
9
10
11
12
13
14
15
1
2
6
10
13
14
7
8
10
11
12
14
15
3
(b)
(d)
Figure I: Illustration of the Rotate step in ChordMixer for N = 16: a) the original Chord protocol, where blue dots are peers, and arrows indicate communications at each hop, b) the sequence before rotation, where the numbers indicate the original position in each track, c) the rotations in different bands, where the ares indicate the rotation sources of new Position O, and d) the rotated tracks. Afterward, each column will be fed to the Mix step of ChordMixer.
We arrange batch learning and inference where the sequences in a batch have the same [log2 N value such that they pass through the same number of blocks. rotate sequences a batch each block separately, then concatenate the rotated for MLP mixing only once. Finally, the mixed tensor is de-concatenated to sequences for block output. There is no padding or chunking in the procedure. Here the key point is that the Rotate layer is cheap, while the Mix layer benefits from the batch-mode acceleration. The same trick does not apply to Transformer-life approaches where dot products and other attention types expensive.
3.3 ANALYSIS
Proposition 3.1. The receptive field becomes full for every output number after O(log, N) blocks.
The proposition is straightforward corollary of Theorem in the Chord paper (Stoica et al. 200T), and we skip the proof here. By this result, not all blocks are needed for every sequence. length-WV sequence passes through only the first [log2 N] blocks, and therethrough the gradient back-propagation.
Definition 3.2.
neural network for D-dimensional inputs full-rank if the network comprises linear layers and elementwise nonlinearities, and all the linear layers have at least rank D.
Proposition 3.3. A ChordMixer block is full-rank on flattened xn f is full-rank.
The proof is given in Appendix A By this result, our method differs from typical bottleneck designs in conventional neural networks that contain low-rank projections. Instead, ChordMixer is wide neural nerwork that directs the input signal towards the learning targets in a broad way.
Next, analyze the complexity of ChordMixer:
4

---

Published as a conference paper at ICLR 2023
Because the Rotate layer is parameter- free, all learnable parameters in ChordMixer block are w. For the two-layer MLP implementation of f, there are O(dh) parameters in one block. Overall, a ChordMixer network has O(hh log2 Nmax) learnable parameters.
The Mix step dominates the running time, The MLP mixing in each block costs ((dhN) and thus OddhN log2 N) for all blocks.
The memory cost for a length-N sequence passing a ChordMixer network is OdN log, N). If we employ the Reversible Residual Network trick (Gomez et al. 2017) to avoid storing intermediate activations, the memory cost can be reduced to O(d.).
3.4 COMPARISON TO RELATED WORK
recent neural attention model called Paramixer (Yu et al. 2022a) also uses the Chord protocol for token mixing. It employs similar mixing MLPs over channels. Differently, Paramixer decomposes an attention matrix into several sparse factors. The non-zero structure of the sparse factors specified by the Chord protocol, and their values are parameterized by multilayer perceptrons. Paramixer assumes that the input lengths are the same. Otherwise, truncation or padding is required to ensure the same length.
PoolFormer (Yu et al., 2022b) is another neural attention model which employs a non-parametric operator over positions. Different from the track rotations in ChordMixer, PoolFormer applies pooling over a local window around every position. The pooling connects all elements within the window and thus has similar role for information propagation. However, defining such windows requires extra assumptions on locality. Despite success in vision and speech, the locality assumptions may not apply other types of sequential data,
shall see in the experiments.
Some other methods organize the sparse connections in hierarchical manner (e.g., Goller & Küchler 1996; Choi al., 2018 Lea et al. 2016). Although they achieve full-receptive field with fewer connections, the hierarchy breaks the symmetry: some elements (or positions) become closer the output than others. The artifact is undesired for neural attention because good attention model should allow each sequence element to have a (nearly) equal chance to interact with the others. In contrast, the design of ChordMixer is decentralized, where no element or position is below or above another. When passing through ChordMixer network, every output position can receive information from all input positions with nearly the same probability (see Appendix G
There is a theoretical equivalence between ChordMixer and a comprehensive convolution: each output track equals the sum of log, N convolutions, where each convolution applies to the corresponding input track. The first of the log, N convolution is 1 1, while each of the rest uses different dilation, kernel size 1, circular padding, and causal connection (self-excluding). However, such a convolution is impractical because 1) current software supports such complicated convolution, and 2) the convolutions have to be run track by track, which is much slower than the proposed rotate-mix steps.
EXPERIMENTS
In this section, we test the scalability and performance of ChordMixer in three different domains: 1)
an arithmetic task with long-range dependence between sequence elements, 2) long text document
classification, and 3) taxonomy classification based on DNA sequences. In the tasks, ChordMixer is
compared with many other existing neural attention approaches, including Transformer Vaswann
al. 2017). Reformer (Kitaev et al. 2020p, Linformer (Wang al. 2020). Nyströmformer (Xiong
et al. 2021), Luna (Ma et al. 2021). Longformer (Beltagy et al. 2020), Cosformer (Qin et al. 2022
Poolformer (Yu et al.) 2022b), and Structured State-Space sequence model (S4) (Gu et al. 2022
For all methods, we used a validation set to tune their hyperparameters (details in Appendix Ch. For
completeness, we also include Recurrent Neural Network (LSTM:; Hochreiter & Schmidhuber) 1997).
Recursive Neural Network (TreeLSTM: (Chi et al., 2018), conventional convolution network (ID
CNN), hierarchical convolutional network (TCN; Lea et al. 2016) in the comparison. All experiments conducted on Linux machine with 8xNV IDIA Tesla V100-32GB GPUs.
5

---

Published as a conference paper at ICLR 2023
length À Log-Noore NornNoormala o²)
peu.s
Frequency
5000
U-1,11
0.2
-.11
-0.6
0.83
0.57
4000
3000
{0,1}
2000
1000
+ 0.83
Target 0.5
0.76
50000
100000 150000 200000 250000 Sequence Length
4
Figure 2: (Left) one instance of the Adding problem with variable lengths. Lengths are sampled from Log-Normal distribution and times with a base length (A). (Right) example of sequence lengths distribution for = 16k. The dashed vertical lines correspond to the percentiles the distribution.
À 200, longest 6.7k
A
1k, longest 31.8k
100
100
Accuracy,
Accuracy,
60
20
20
10 20
30
60
70
80
90
95
99.5
10
20
30
50
60
70
80
90
95
99
99.5
Sequence Length Percentile
Sequence Length Percentile
16k, longest 242.4k
A 128k, longest 1.5M
100
100
80
80
Accuracy,
20
10
99.5
10
95
99.5
Sequence Length Percentile
Sequence Length Percentile
Random Cuess
Linformer
Ryftrmmoomer
54
Cosformer
TreelSTM
1D CNN ChoraMizer
Transformer
Reformer
Pootformer
Figure 3: Prediction accuracies of the Adding problem with sequences of variable size. À controls the mean length of the sequences. The mean scores and error bars across 3 runs are plotted. For X 16k and A 128k, drop some architectures in the plots because they ran out memory.
4.1 ADDING PROBLEM WITH VARIABLE LENGTHS
The Adding problem is a synthetic task inspired by Hochreiter Schmidhuber (197)). This is regression task used to test networks ability to detect relevant tokens and perform the sum operation on them. Each element of an input sequence is pair of numbers (a,,b;), b:), where a; ~ (111,),, E {0, 1), I,..., N. We generated signals at randomly selected positions ( and such 0.5 + de, ata Unlike Hochreiter & Schmidhuber (199);; Khalitov al. (2022), generated sequences with different length N = round(A <) and LogNoraa "),, where μ 0.5, o 0.7, and À is a base length. The resulting length distribution is left-skewed and has wide spread (see 2ight)) The
that b,, bio and b; elsewhere. The learning target

---

Published as a conference paper at ICLR 2023
variable lengths bring extra challenge to the task. In evaluation, network prediction ğ is considered correct if ly 9 < 0.04. A sequence example is illustrated on Figure (left).
In the experiment setup, used four different A's: 200, 1k, 16k, and 128k. For each X, generated 60,000 learning instances (sequences and their targets). A larger corresponds to a more difficult task. For example, when À 200, the longest sequence has a length of 6.7k, while X 128k leads to the longest sequence up to 1.5 million elements. Figure 2 (right) shows the histogram of sequence lengths with À 16k.
Figure 3 shows the comparison results. The tested models worked perfectly in the easiest setup (x With increasing À some methods started fail. For example, Reformer performed as poorly as random guessing for À = 1000. Transformer, Nyströmforner, Linformer, and S4 also had more or less degraded accuracies when 1000. When À 16k and the longest sequence becomes 242K, three methods (Transformer, Reformer, and Luna) ran out of memory and could not finish training. Only ChordMixer, Cosformer, and Nyströmformer achieved more than 80% accuracy, while the others got close to random guess. ChordMixer was the only method that reached nearly 100% for = 16k. When 128k, only ChordMixer and Cosformer finished training, while the methods had out-of-memory errors. ChordMixer still achieved almost 90% accuracy for all sequences, while Cosformer became inaccurate for the 10% longest sequences.
4.2 LONG DOCUMENT CLASSIFICATION
Long Document Classification, longest 131k
This task measures the performance of Chord- Mixer in modeling complex long-term depen- dencies for very long texts. The data set consists of a collection of academic papers and is pub- licly available
100
90
Accuracy,
Github. Following He et al.
70-
(2019), we used four classes of the documents: es.AI, NE, math.AC, math.GR, GR, which results in data set of 11956 documents. We split the data into 70% training, 20% validation, and 10% test sets. Unlike the original research (He al. 2019). we encoded each document on the character level and formed a more challenging task. The minimum, median, and maximum lengths of the documents are 4.5k, 39k, and 131k, respectively. All compared methods ex- cept ChordMixer used zero padding to align with the maximum length.
50-
Nyströmformer
Longfomer Confomme
ChordMixer
Poolformr
40
10
30
40 50 60 80 90
99 99.5
Sequence Length Percentile
Figure 4: Accuracies in the Long Document Clas- sification task at different length percentiles.
Figure shows the classification accuracies. ChordMixer performs the best, where the only method that achieves nearly or above 80% accuracy at all percentiles. Nyströmformer is good as ChordMixer at 60% sequence length percentile, while it becomes worse and worse for longer documents. Cosformer achieves around 70% accuracy at all percentiles. The accuracies of PoolFormer are lower than 70% almost everywhere and as low as 55%. The accuracies of Longformer fluctuate around 70%. Five other compared methods (Transformer, Linformer, Reformer, $4, and Luna) ran out of memory, and we have to drop them from the comparison figure.
4.3 DNA SEQURNCE-BASEI TAXONOMY CLASSTFICATION
Next, test ChordMixer and other compared methods in biology. We have downloaded DNA sequences from the Genbank database as well as their taxonomic labels. Then we organized four binary classification tasks (ordered by the maximum sequence length):
1. Carassius vs. Labeo. This a small data set with 7263 genes for Carassius (a kind of fish) and 6718 sequences for Labeo (another kind of fish). The shortest sequence has 79 base pairs, while the longest one has 100101. In terms of the required scalability of the tested models, this task is the easiest problem within this section.
httts:///www.t nlm. www.miihh.../ggeaan.....
7

---

Published as a conference paper at ICLR 2023
Carassius Labeo
Mus Rattus
100
100
90
90
ROC-AUC,
ROC-AUC,
50
99.5
10
20
90 Sequence Length Percentile
30 40
50
60
70 a0
95
99 99.5
Sequence Length Percentile
Danio vs. Cyprinus
vs. Bos
100
100
ROC-AUC,
ROC-AUC,
50
50
10
20 30
40
50
60
70
80
90
95
99
99.5
10
20
30
90 95 99 99.5 Sequence Length Percentile
40
50
60
70
80
Sequence Length
Transformer
Reformer
Poalformer
LSTM
ChardMixer
Linformer
Nystromformer
Cosformer
Longfarmer
Figure 5: Test ROC-AUCS on the DNA-based taxonomy classification tasks. The score is the average of three runs with different random seeds. Plots better read in colors.
2. Mus vs. Ratfus. This data is the heaviest among used within this problem setup the genus level. The classes are strongly imbalanced, differing in size by almost factor of two. The task is to classify gene as rat (rattus) or mouse (mus). There are 275636 Mus and 1333 10 Rattus sequences, with minimum and maximum sequence lengths of 32 and 261 261093, respectively.
3. Danio vs. Cyprinus. Both genera belong to the cyprinidae family, where danio is small freshwater fish, and cyprinus is genus of carps. The shortest gene consists of 34 bases, while the longest has 261943. Classes have imbalanced: 47135 Danio and 83321 Cyprinus sequences.
4. Sus Bos. Both genera belong the Vertebrate organisms group, where sus and bos roughly correspond to domestic pigs and cattle, respectively. Although the genera are nearly balanced (51973 sequences for bos and 50027 for sus), the data set the most challenging because the lengths are highly different (shortest 63 and longest 447010).
We chose these four classification tasks because the taxa have similar length distribution, and is difficult classify them only by sequence length (statistics in Appendix
We have used Area under the receiver operator curve (ROC-AUC) the evaluation metric to overcome the class imbalance effect. All models were trained using cross-entropy loss, with empirical class weights calculated on the training set. The train/validation/ees split was stratified to ensure equal class distribution within these data sets. We have applied zero padding to the maximum sequence length for all compared models except ChordMixer. For Transformer, Reformer, and Linformer, the sequences were truncated to the length such that they do not throw an out-of -o--o---ooory error.
Figure 5 shows the ROC-AUC results of the four taxonomy classification tasks. ChordMixer stands at the top or near the top at almost all sequence length percentiles for all data sets. Especially at the right end of every plot, our method achieves substantially higher ROC-AUC than all other approaches, which shows that ChordMixer has a clear win over those methods which require zero padding. For the smallest data set (Carassius Labeo), several methods comparable to ChordMixer for short
8

---

In our design, we do not assume any local patterns in the data to endow nearly equal chance for all tokens to interact with each other. If specific local patterns prevail in the data (e.g., Markovian property in images), our method might require more training data than approaches that use locality Published as a conference paper at ICLR 2023
sequences. However, starting from the 99 percentile (corresponds to sequence length 5630), all other compared methods experience a significant performance drop. For the longest part (99.5 percentile in Sus Bos), ChordMixer achieves 89% ROC-AUC, while all other methods are below 70%. With increasing maximum sequence length, ChordMixer wins at more length percentiles. For Danio vs. Cyprinus and Sus Bos, ChordMixer is clearly the best nine of ten listed percentiles. Interestingly, ChordMixer is the only method that achieves stable ROC-AUC (around 84-89%) across various lengths for the Sus vs. Bos data set.
4.4 ABLATION STUDY
In the above experiments, every learning system comprises neural attention part and a predictor (regressor or classifier). Here we perform an ablation study to show that the main improvement comes from the ChordMixer the neural attention part and not from the predictor.
We chose the Carassius vs. Labeo taxonomy classification task for the ablation study. Besides ChordMixer, we included two other compared methods, Poolformer and Cosformer, because their overall accuracy or ROC-AUC seem to be more competitive than the rest (others' results in Appendix E to avoid clutter). Each neural model was combined with two different predic- tors: AVG) averaging followed by linear classi- fier as we used in the above ChordMixer results,
Carassius vs. Labeo
100
80
ROC-AUC,
60
Pesiformer
Peoiformar
Cosformer
Poolformr FLAT
Costormer FLAT
and CLS) using classification token in the neu- ral attention and then applying linear classifier. For Poolformer and Cosformer, also tried a linear classifier on the flattened output from neural attention (FLAT).
10
20 30 40
60
70
80
90 95 99 99.5
Sequence Length Percentile
Figure 6: Ablation study different combinations of neural attention models and classifiers.
In Figure 6 ChordMixer, either with CLS or AVG, wins for all sequence lengths except the 20 and 95 percentiles. Even with the same classifier, both Poolformer and Cosformer perform worse than ChordMixer. The FLAT strategy sometimes im- proves ROC-AUC for the competing models but still cannot surpass ChordMixer most percentiles.
CONCLUSION AND FUTURE WORK
We have proposed effective neural attention model ChordMixer for long sequences with variable lengths. The building block of our model contains two simple layers: oon-aaraettric multi-scale rotation and channel mixing. ChordMixer does not require chunking or padding at all and easily scales to a maximum sequence length of 1.5 million in our work. We have provided experiments from different domains, where our method has outperformed many other recent approaches.
In our method, sequences pass through variable number of ChordMixer blocks, depending on their lengths. We have found practical issues far for such a con-conventional setting. However, it challenges theoretical analysis because the mapping function space becomes more complicated, which demands more advanced mathematical tools.
as an inductive bias. In the future, we could study how to learn such patterns using our model with massive self- supervupee masked training. Relative position information could be incorporated (in an economical way) to facilitate pattern learning.
9

---

Published as a conference paper at ICLR 2023
ETHICS STATEMENT
is implausible that our work would bring potential negative societal impacts. We have proposed a basic methodology for machine learning. Our research has no connection weapons, surveillance systems, adverse experiments, or privacy and security issues. Therefore, there is little risk of harmful applications for living beings and human rights. Moreover, our findings benefit the environment by substantially reducing the computational complexity in neural attention models.
Our work also fulfills the requirements from the ICLR Code of Ethics. The research does not use human-derived data. For the synthetic data set generated by we publish the data generation code (under the MIT license). For the public document corpus and genome (non-human) data set, we have followed the usage requirement from the data provider and cited their contributions. There are no domain-specific considerations when working with high-risk groups because our work does not involve research on human beings. Our data does not contain offensive content. Moreover, our work complies with GDPR because we do not reveal sensitive personal information.
10

---

Published as a conference paper at ICLR 2023
REFERENCES
Joshua Ainslie, Santiago Ontanon, Chris Alberti, Vaclav Cvicek, Zachary Fisher, Philip Pham, Anirudh Ravula, Sumit Sanghai, Qifan Wang, and Li Yang. ETC: Encoding long and structured inputs in transformers. In Proceedings of Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 268-284, 2020.
Ziga Avsec, Vikram Agarwal, Daniel Visentin, Joseph Ledsam, Agnieszka Kyle R Taylor, Yannis Assael, John Jumper, Pushmeet Kohli, and David R Kelley. Effective gene expression prediction from sequence by integrating long-range interactions. Nature methods, 18 (10):1196-1033, 2021.
Iz Beltagy, Matthew Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv, 2004.05150, 2020.
Jihun Choi, Kang Min Yoo, and Sang goo Lee. Learning to compose task-specific tree structures. In The Thirty-Seoond AAAI Conference on Artificial Intelligence, pp. 5094 5 5101, 2018.
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, David Belanger, Lucy Colwell, and Adrian Weller. Rethinking attention with performers, arXiv, 2009.14794, 2020.
William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity, arXiv,
2021.
Gilad Fuchs, Yoav Voichek, Sima Benjamin, Shlomit Gilad, Ido Amit, and Moshe Oren. 4sUDRB- seq: measuring genomewide transcriptional elongation rates and initiation frequencies within cells. Genome Biology, 15(5):1-10, 2014.
M. Gasperini, J. M. Tome, and J. Shendure. Towards a comprehensive catalogue of validated and target-linked human enhancers. Nature Reviews Genetics, 21:292-310, 2020.
C. Goller and A. Küchler. Learning task-dependent distributed representations by backpropagation through structure, In Proceedings of International Conference on Neural Networks, pp. 347-352, 1996.
Aidan N Gomez, Mengye Ren, Raquel Urtasun, and Roger B Grosse. The reversible residual network: Backpropagation without storing activations. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations (ICLR), 2022.
Jun He, Liqun Wang, Liu Liu, Jiao Feng, and Hao Wu. Long document classification from local word glimpses via recurrent attention learning. IEEE Access, 7:40707-400 4070077-478,, 2019.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1997.
Andrew Jaegle, Felix Axel Gimeno Gil, Andy Brock, Oriol Vinyals, Andrew Zisserman, and Joao Carreira. Perceiver: General perception with iterative attention. In International Conference Machine Learning (ICML), 2021.
Ruslan Khalitov, Tong Yu, Lei Cheng, and Zhirong Yang. Sparse factorization of square matrices with application neural attention modeling. Neural Networks, 152:160-163 2022.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv, 2001.04451, 2020.
Colin Lea, Rene Vidal, Austin Reiter, and Gregory D Hager. Temporal convolutional networks: A unified approach to action segmentation. In European Conference on Computer Vision, pp. 47-54, 2016.
11

---

Published as a conference paper at ICLR 2023
Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In International Conference Computer Vision (ICCV), 2021.
Ze Liu, Han Hu, Yutong Lin, Zhuliang Yao, Zhenda Xie. Yixuan Wei, Jia Ning, Yue Cao. Zheng Zhang, Li Dong, Furu Wei, and Baining Guo. Swin transformer v2: Scaling up capacity and resolution. In International Conference on Computer Vision and Pattern Recognition (CVPR). 2022.
Xuezhe Ma, Xiang Kong, Sinong Wang, Chunting Zhou, Jonathan May, Hao Ma, and Luke Zettle- moyer. Luna: Linear unified nested attention. Advances in Neural Information Processing Systems, 34, 2021.
Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A Smith, and Lingpeng Kong. Random feature attention. arXiv, 2103.02143, 2021.
Zhen Qin, Weixuan Sun, Hui Deng, Dongxu Li, Yunshen Wei, Baohong Lv, Junjie Yan, Ling- peng Kong, and Yiran Zhong. cosformer: Rethinking softmax in attention. arXiv preprint arXiv:2202.08791, 2022.
S. J. Sharp, J. Schaack, L. Cooley, D. Burke, and D. Söll. Structure and transcription of eukaryotic (RNA genes. CRC Critical Reviews in Biochemistry, 19(2):107-144, 1985.
Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, and Hari Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Computer Communication Review, 31(4):149-160, 2001.
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: benchmark for efficient transformers. arXiv, 201 1.04006, 2020.
Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey, ACM Computing Surveys, 2022.
C. N. Tennyson, H. J. Klamut, and R. G. Worton. The human dystrophin gene requires 16 hours to be transcribed and is cotranscriptionally spliced. Nature Genetics, 9:184-190, 1995.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv,, 2006.04768. 2020.
Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmformer: A Nyström-base based algorithm for approximating self-attention. arXiv, 2102.03902. 2021.
Tong Yu, Ruslan Khalitov, Lei Cheng, and Zhirong Yang. Paramixer: Parameterizing mixing links in sparse factors works better than dot-product self-attention. In International Conference Computer Vision and Pattern Recognition (CVPR), 2022a.
Weihao Yu, Mi Luo, Pan Zhou, Chenyang Si, Yichen Zhou, Xinchao Wang, Jiashi Feng, and Shuicheng Yan. Metaformer is actually what you need for vision. In Conference on Computer Vision and Pattern Recognition (CVPR), 2022b.
Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang. Li Yang, et al. Big Bird: Transformers for longer sequences. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
12

---

Published as a conference paper at ICLR 2023
A PROOF OF PROPOSITION 3.3
Proof. A ChordMixer block contains a Rotate layer and a Mix layer. Below we show that both layers full-rank.
The Rotate layer re-orders the numbers in the matrix. Therefore, it is equivalent to left-multipliing the flattened zT with the corresponding permutation matrix. Because permutation linear and full-rank, the Rotate layer is full-rank.
The Mix layer applies f on the columns (tokens). By the assumption, f full-rank network that contains element-wise non- non-lineesssiees and linear operators. Each linear operator is equivalent to left-muliplyinng block-wise matrix with the column-majo flattened input z, where each block in the multiplying matrix is the linear weights W. The following illustrates the first linear operator, where flattened output equals
W
T;1
0
W
0
J,2
0
W
I;3
:
0
0
W
T.N
Because W has at least rank d, the whole multiplying matrix has at least rank dN, Therefore, the Mix layer is full rank.
B DATA PREPARATION
Carassius Labeo
Mus Ratlus
17500
1200
15000
1000
000
10000
600
7500
5000
14
16
3.
18
log
Danio vs. Cyprinus
Sus vs. Bos
Daria
14000
Sua
12000
5000
hrssunc
6000
4000
4000
2000
2000
Figure 7: Sequence lengths distribution for the DNA-based taxonomy classification task.
Here we provide extra information about data preparation the three groups of experiments
Adding problem. For each setup, we generated 60, 000 data instances (including training, validation. and test sets), except for the hardest task. The reason for the exception is that all sequences are padded to the maximum length, and storing so many long tensors requires enormous hard disk space and heavy RAM for reading. With À =128k, the longest among 60, 000 generated sequences has over three million elements, which cause all compared methods except ChordMixer out of
13

---

Published as a conference paper at ICLR 2023
memory. Therefore, reduced the number of generated sequences to 12, 000 for À = 128k for more reasonable comparison.
Because there only two input channels in the raw sequences, used linear module augment the embedding space to higher dimensions. For ChordMixer, the embedding layer outputs channels, where d equals TrackSize times log2 Nmax. The number of channels for the other compared methods, ranging from 32 to 128, are tuned by hyperparameter search (see Section for details).
Long document classification. There a few documents extremely long (longest=2, 483, 331). Because all compared methods except ChordMixer padded zeros to align with the longest, they are easily prone to out-of-memory reasonable comparison. There are 56 among 11956 documents ( 0.47%) longer than 131k, and we discarded their tailing part beyond 131k (no compared method has access the discarded tailing part).
Therefore, we used the maximum length of 131k for more
DNA-based faxonomy classification. The GenBank collection contains massive genes from many taxa. However, not all branches in the taxonomy tree are suitable for comparing neural attention models. Quite often, the taxa can easily be separated by the gene lengths. Here we particularly chose four classification tasks where the involved taxa have overlapped length distributions. See Figure for sequence length histograms in the tasks, where we can see that it is hard classify the taxa using their lengths solely.
14

---

Published as a conference paper at ICLR 2023
C MODEL CONFIGURATIONS AND TRAINING DETAILS
In this section, we provide the full set of hyperparameters used to train models and report their results. The final hyperparameters were chosen based on the Bayesian optimization algorithm with a 32GB GPU memory constraint. After the best hyperparameters selected by the minimum validation loss, we applied the corresponding model to the test set and report its performance.
The adding problem is regression task, where we used the MSE loss. The other two tasks are classification, where we used the cross-entropy loss, with class weights, calculated on the training set, to overcome the class imbalance effect. Adam optimizer with task- and model-specific learning rates was used for all problems.
The training configuration and hyperparameters for each neural network and problem are summarized Table T and Table For the adding problem, we used the same hyperparameters across all setups.
Table 1: The final competitors' hyperparameters used in experiments. L, H, E, and P refer to number of layers, number of heads, embedding size, pooling strategy, respectively. Dash ("-") indicates that corresponding parameter is not present the architecture.
Task. Adding
Model
L
H
E
P
LearningRate
BatchSize
Transformer
4
64
FLAT
0.0005
Linformer
2
128
FLAT
0.0001
10
Reformer
2
64
FLAT
0.0003
Cosformer
2
128
FLAT
0.0005
Poolformer
2
2
128
FLAT
0.0005
10
Luna
32
FLAT
0.0005
S4
32
FLAT
0.0005
Nyströmformer
2
128
FLAT
0.0002
Long Document
Cosformer
2
64
FLAT
0.0005
10
Classification
Poolformer
2
64
FLAT
0.0005
10
Nyströmformer
2
128
FLAT
0.0005
10
Genbank
Transformer
2
128
TRUNC
0.0005
C/L.
Linformer
2
128
TRUNC
0.0005
Reformer
2
64
TRUNC
0.0005
Cosformer
2
128
FLAT
0.0003
Poolformer
2
2
128
FLAT
0.0003
Nyströmformer
2
128
FLAT
0.0002
Genbank M/R
Transformer
2
128
TRUNC
0.0005
Linformer
2
128
TRUNC
0.0005
Reformer
2
64
TRUNC
0.0005
Cosformer
2
128
FLAT
0.0005
Poolformer
2
128
FLAT
0.0005
Nyströmformer
2
2
128
FLAT
0.0005
Genbank D/C
Transformer
2
128
TRUNC
0.0005
Linformer
2
128
TRUNC
0.0005
Reformer
2
64
TRUNC
0.0005
Cosformer
2
64
FLAT
0.0003
Poolformer
2
2
64
FLAT
0.0003
Nyströmformer
2
64
FLAT
0.0002
Genbank S/B
Transformer
2
128
TRUNC
0.0005
Linformer
2
128
TRUNC
0.0005
Reformer
2
64
TRUNC
0.0005
Cosformer
2
64
FLAT
0.0003
Poolformer
2
64
FLAT
0.0003
Nyströmformer
2
64
FLAT
0.0002
15

---

Published as a conference paper at ICLR 2023
Table Hyperparameters used train ChordMixer. h and P refer hidden layer size and pooling strategy, respectively. The embedding size is TrackSizex logz Nmax.
Task.
h
TrackSize
LearingRate
BatchSize
Adding
128
16
AVG
0,0001
2
Long Document Classification
196
16
AVG
0.0002
Genbank C/L
128
16
AVG
0.0001
2
Genbank M/R
128
16
AVG
0.0001
Genbank D/C
128
16
AVG
0.0001
2
Genbank S/B
128
16
AVG
0.0001
2
LRA Image
420
28
AVG
0.01
100
LRA Text
96
16
AVG
0.007
90
LRA Listops
88
8
AVG
0.007
150
LRA Retrieval
128
12
AVG
0.007
90
LRA Pathfinder
320
24
AVG
0.005
150
LRA PathfinderX
128
10
AVG
0.001
120
D CHORDMIXER ATTENTION EXAMPLE
Every ChordMixer block outputs d N matrix. We visualize the matrices to study how the model attends to different positions. We trained a neural network for the Adding problem with 200, where the shortest and longest sequences have lengths 32 and 6655, respectively. Figure shows source sequences and the resulting matrices after applying the first and the last ChordMixer block (denoted by output, and output We investigated three sequences with different lengths: 40, 240, and 1006.
As we can see in the top track (the non-rotated track), ChordMixer correctly identifies the relevant positions around the markers. The pattern is clearly visible for all sequences and in both output and aut
output,. high values basically reflect the rotation scales, while output the pattern spreads wider. Especially, outputast demonstrates multi-scale attentions, where the upper tracks (i.c., those with no or scall-scale rotations) show local attentions, while the lower tracks (i.c., with larger-scale rotations) show
values.
16

---

Published as a conference paper at ICLR 2023
Sequence length 40
Sequence length 240
56
Sequence length 1006
45
Figure 8: Visualizations of three examples in the Adding problem (A 200) with the ChordMixer model. The examples have different lengths. For each example, the upper chart corresponds to the input sequence, where the color map ranges from red (-1) black (+1), with white correspond to O; the middle and bottom charts are matrices after applying the first and the last ChordMixer blocks, respectively.
17

---

Published as a conference paper at ICLR 2023
E MORE RESULTS FROM ABLATION STUDY
In the main paper Section 4.4, we have included ChordMixer, Poolformer, and Cosformer, with three pooling strategies CLS, AVG, and FLAT. Here provide extensive results, including four other models (Transformer, Reformer, Linformer, and Nyströmformer) and two other strategies (TRUNC and SEGM).
TRUNC means truncation. That is, a sequence is longer than the truncation threshold 1 (we used 16k), the part longer than & is discarded. For sequences shorter than y/, we padded them to length v. In TRUNC, the attention model output is flattened and followed by a linear predictor.
SEGM means segmentation. If sequence is longer than the segmentation threshold (we used 3 = 2000), it is chunked into segments of length B. For sequences shorter than 3, we padded them length 3. The compared methods using SEGM are first applied all segments. Then the predictor outputs on individual segments are averaged for the final decision. Different from TRUNC, SEGM allows the compared method access all elements a sequence.
TRUNC and SEGM were used for those models that are not scalable for the whole longest sequence, where only pieces of the sequences are fed to the models. These strategies assume that the character- izing patterns appear only locally (within v or (8). However, they might lose information because they drop long interactions in the truncation or segmentation.
The more extensive ablation study results are shown in Figure 9 The conclusion in the main paper remains: our method better than the other compared methods even for all tested strategies. ChordMixer achieves the best ROC-AUC in most sequence length percentile, especially for the long sequences. The additional compared methods and strategies do not lead to better results.
Carassius Labeo
100
ROC-AUC,
Transfomer CLS
Reforma CLS
Unformr CLS
Nostrenfemme CLS
Tooiformer AVG
Contommr PLAT
Trandhmer ANG
Refomee AvG
Untommr
Nystrtnfommr AUG
Rontoorerr AT
ChorM aer
Tranalsmer
netomm
Untomer SEOM
Rosi-enterme
Castommrr CLS
Charch
Tranalsmor TRUN:
TRLNC
fome
Costemmer
10
20
40
50
60
70
80
90
95
99.5
Sequence Length Percentile
Figure 9; Ablation study on seven neural attention models with different pooling methods. Figure is better read in colors.
F PADDING STRATEGY
For the results reported in the main paper used zero padding to the maximum sequence length across the whole data set (Pad to Overall Max). However, some used methods allow using different sequence lengths during training. For such methods zero-pad sequences to the maximum sequence
18

---

Published as a conference paper at ICLR 2023
length in a batch (Pad to Batch Max) to further improve training and inference speed. We also empirically verified that there is no significant change in resulting performance when switching padding strategies (see 3).
Table 3: Accuracy comparison of different models with two pooling strategies the Long Document Classification task. Pad to Overall Max and Pad to Batch Max denote padding to the maximum sequence length in the whole data and in batch, respectively. Reformer gets Out-of-Memory error in both setups even when processing sequence by sequence.
Model
Pad to Overall Max
Pad to Batch Max
LongFormer
75.3%
75.7%
Nyströmformer 73.1%
73.0%
Poolformer
67.0%
68.
Cosformer
72.3%
72.6%
Reformer
Out-of-Memony
Out-of-Memory
G EMPIRICAL STUDY ON REACHING PROBABILITIES IN A CHORD NETWORK
At first glance, the Chord connection protocol looks asymmetric: in each hop, node is connected to few specific nodes in one direction. There is question: if we perform a random walk from one node, how are its reaching probabilities to all nodes after several hops? It has been shown in the original Chord paper that any node can use Ollog, N) hops to reach all N nodes. Here we perform an empirical study on the distribution of the reaching probabilities.
We consider N = 5000 for example. We first normalize the adjacency matrix of the Chord graph A to sum to 1). Denote A the normalized matrix. Then Å N+11 A gives the reaching probabilities from one node to another (including itself) after 14 hops. Because the circle is symmetric, we can pick any source node, e.g., the first, and plot the histogram of its reaching probabilities to all nodes as targets.
be right stochastic (i.e.,
The result is shown in Figure 10 We can that the reaching probabilities concentrate around the uniform probability 2 x 10-1 with a small deviation (std=3 x 10-5), which justifies that in a ChordMixer network, each output position receive information from all input positions with nearly equal chance.
700
500
400
300
100
0
0.5
2
2.5
3.5
110
Figure 10: Histogram of reaching probabilities from a node all nodes in Chord network for N 5000.
19

---

Published as a conference paper at ICLR 2023
H PEAK MEMORY AND RUNNING TIME COMPARISON
Table Comparison of peak memory (GB) and average running time (milliseconds) per sequence for the Adding problem. For all models, except for Linformer, applied padding the maximum sequence length within a batch. We have used a Linux machine with one Tesla-V100 V100 GPU (32GB memory).
Model
À 200 (longest=6.7k)
X
128k (longest=1.5M)
Peak Memory
Running Time
Peak Memory
Running Time
LSTM
1.5
460
Tree-LSTM
25.3
9831
ID-CNN
1.4
3.3
TCN
1.4
5.1
Transformer
1.9
9.8
Linformer
1.6
12.5
Reformer
2.0
23.3
Longformer
1.7
11.1
Luna
1.7
16.6
S4
1,4
3,2
Poolformer
1.4
3,9
13.6
378
Cosformer
1.5
8.7
22.6
994
ChordMixer
1.5
4.9
23.1
604
I LONG RANGE ARENA PUBLIC BENCHMARK
We compared ChordMixer with Transformer and several of its variants on the Long Range Arena benchmark (Tay al., 2020). Table [ shows the accuracies of the compared methods on five LRA tasks. We can see that ChordMixer is substantially more accurate than the X-formers in all tasks. Similar to (Tay et al. 2020, Figure 3), we add ChordMixer to the plot the relationship between accuracy and inference speed/memory footprint (see Figure TTP. As can see, ChordMixer consumes a similar amount memory as the approximated variants of Transformer. Although Nyströmformer, Linformer, and Performer faster, they sacrifice much prediction accuracy (more than 20% below ChordMixer).
Table Classification accuracy of ChordMixer and X-formers on the LRA tasks. The performance of the competing models was taken from Tay al. 2020 and Xiong al. (021). Boldface numbers are winners in each task, while the underlined are runner-ups.
Model
ListOps
Text
Image
Retrieval
Pathfinder N 1024
PathfinderX
N = 2000
N
4000
N 1024
N 4096
16384
Transformer
36.37
64.27
42.44
57.46
71.40
Longformer
35.63
62.58
42.22
56.89
69.71
X
Linformer
37.70
53.94
38.56
52.27
76.34
X
Reformer
37.27
56.10
38.07
53.40
68.50
X
Performer 18.01
65,40
42.77
53.82
77.05
X
Nyströmformer
37.15
65.52
41.58
79.56
70.94
X
ChordMixer 60.12
88.82
89.98
90.17
96.69
98.63
We do not include LRA in our main paper because it is not suitable for our problem setting: the sequences in each LRA task have the same length, and they rather short compared to those in experiments. See the statistics in Table
20

---

Published as a conference paper at ICLR 2023
Long Range Arena
90
ChordMixer
Average accuracy
80
Nystromformer
60
Transformer
Linformer
50
Reformer
Performer
40
0
100
150
200
250
350
Instances per second at test time.
Figure 11: Accuracy (y-axis), speed (x-axis), and memory footprint (size of the circles) of different models measured the LRA benchmark at test time.
Task source
Task name
Sequence length
LRA
ListOps
2K
LRA
Text
4K
LRA
Retrieval
4K
LRA
Image
IK
LRA
PathFinder
IK
LRA
PathFinder-X
16K
Our experiments
Adding problem (base length=128k)
min 32, median 134k, max 1.5M
Our experiments
Long document classification
min 4.5K, median 39K, max 131K
Our experiments
Carassius vs. Labeo
min 79, median 651, max 100K
Our experiments
Mus vs. Rattus
min 32, median 979, max 261K
Our experiments
Danio vs. Cyprinus
min 34, median 868, max 261K
Our experiments
Sus vs. Bos
min 63. median 664, max 447K
Table 6: Length statistics of the data sets in our experiments and the Long Range Arena (LRA) data
sets
21

---

Published as a conference paper at ICLR 2023
J SELF-SUPERVISER PRE-TRAINING WITH CHORDMIXER FOR GENETIC VARIANT CLASSIFICATION
In the main paper, focused ChordMixer for supervised learning tasks. We have been developing a framework where ChordMixer is used for self-supervised pre-training as well. Here we present some preliminary results for genetic variant importance prediction using DNA sequences.
An essential task in biology is to predict the influence of genetic variants on cell-type-specific gene expression, in order to inform fine-mapping of the many thousands of noncoding associations with phenotypes of interest from genome-wide association studies (GWAS). A genetic variant comprises segment of gene sequence, a varied position, and the varied base at the position. The Genetic Variant Classification task is to predict whether given variant effect is significant or not.
We have used the data set collected by Avsec et al. (202T). For self-supervised pre-training, we followed the Masked Language Modeling approach by using the non-masked bases (70%) to infer the masked bases (30%). In the pre-training, we have used over 100,000 randomly sampled human gene segments. The pre-training network employs the autoencoder architecture, where both encoder and decoder are ChordMixer networks. For supervised learning (fine-tuning) we extracted DNA sequences with up to 20k sequence length to construct the data set. which includes 97 992 instances over 49 tissues. In classification, we employ a light-weight classifier (average pooling + linear classifier) with the features output from the pre-trained encoder.
Table 7 shows the preliminary results, where we compared ChordMixer with the SOTA method in the field Enformer (Avsec et al., (202T). We can see that using ChordMixer the classifier (without pre-training) is already substantially better than Enformer. The ROC-AUC is further improved by 3.7% by using the pre-trained encoder feature extractor.
Table 7: Preliminary results of comparing Enformer and ChordMixer on Genetic Variant Classification. The performance metric is the mean area under the receiver operating characteristic curve (ROC- AUC).
Model
ROC-AUCX 100%
Enformer (Avsec et al. 2021
70.5
ChordMixer (without pre- ve--rammigg)
84.9
ChordMixer (with pre-training)
88.1
22


Reviews:
[{"review_id": "MsFKH1EI3eY", "reviewer": "Reviewer_pZas", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a method to extend neural attention to longer text with limited computations. With inspiration from the P2P Chord protocol, it rotates the token indices to allow the model to attend to tokens in different scales of distances. It is proved to have a large receptive field compared to traditional transformers while preserving sublinear space and time complexity. Experiments are conducted on both synthetic arithmetic problems, long document classification, and DNA taxonomy tasks. The proposed method, named ChordMixer, is shown to be more effective than its baseline models.", "summary_of_the_review": "The paper proposes a method that mimics the Chord protocol to allow distant attention for long sequence encoding. Although shown to be effective on newly proposed data, more popular datasets should be used so the results can be more convincing. Also, the novelty of this paper is limited given many pattern-based methods have already been proposed with similar ideas. I would suggest a rejection for this paper.", "strength_and_weaknesses": "Strengths:\n\n1. ChordMixer is theoretically guaranteed to have sublinear time and space complexity, which makes it efficient on long sequence tasks.\n2. The proposed method is simple and can be efficiently implemented with modern hardware.\n3. ChordMixer is shown to be effective on the tasks presented in the paper.\n\nWeaknesses:\n\n1. Experiments should be conducted on more standard datasets, e.g. Long-Range Arena. Given that there are tons of work on long sequence transformers, comparing them one by one is unrealistic, thus testing ChordMixer on such a dataset is a preferable way. I would expect the ChordMixer to be a point in fig 3 of Tay et al. (2021) (the LRA paper). Working with a new dataset makes it hard to judge the performance of ChordMixer.\n2. In section 4.2, I don't know why other models all need zero padding to align with the maximum length. Some models, e.g. Reformer and Linformer do not have any constraints on the input length and do not need the inputs to be of equal lengths. \n3. ChordMixer might be viewed as a pattern-based method in the taxonomy of Tay et al. (2020), then some baselines seem necessary. E.g. random pattern can similarly achieve a long receptive field with a high probability, and longformer (sliding window + dilated pattern + global token) can also achieve a large receptive field for relatively long sequences, although I think a larger receptive field does not necessarily lead to better interactions between distant tokens.\n4. The presentation needs to be improved. I would give more details in the next section.\n\nQuestions:\n\n1. In section 2, I don't think Longformer and ETC use learnable side memory modules (or do you mean the global token?).\n2. ChordMixer is designed to have sparse routes, while some sequences, such as natural language, and adjacent tokens could be very important contexts. Do you think ChordMixer may be less efficient to capture this information?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ApzLxpdMmb", "reviewer": "Reviewer_9e1K", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new neural attention model called \"ChordMixer\" to enable long-range interactions for sequences with variable lengths. The proposal takes inspiration from the Chord protocol in P2P networks. The ChordMixer consists of a series of ChordMixer blocks where in each block, an input token with $d/M$ dimensions (M = $log(N) + 1$) first interacts with $k=log(N)$ peers/tokens via the rotation layer. The rotation layer concatenates the representation from peers to its own to get a $d$ dimensional representation for the token. Next, each token is processed by a mixer layer comprising a two-layer MLP which enables sharing of information. A series of $log(N)$ blocks ensure a full-receptive field, i.e., all output tokens can be influenced by each input token.\n                                                                                                      \nExperiments on tasks involving synthetic and real data show that ChordMixer is scalable to very long sequences while outperforming RNNs, CNN, and other efficient attention methods.", "summary_of_the_review": "As explained above, the idea of ChordMixer is novel and the experiments are thorough. Thus I recommend acceptance for this work. \n", "strength_and_weaknesses": "**Strengths** \n    \n- The paper is clearly written. The design of the ChordMixer block is novel, conceptually simple, and well-motivated from the P2P network. The figures on the Chord protocol and the rotate layer make it easy to understand.  \n- The experimental results on the artificial and real-world sequences showcase that ChordMixer outperforms recent efficient attention models when dealing with long sequences. The code in the supplementary and the details should make the work easily reproducible.\n    \n\n**Questions and Weaknesses**:\n\n- Page 1 paragraph 2: \"Although numerous architectures such as Transformer and its variants have been proposed, they usually assume constant input length.\" The assumption/requirement stems from efficient GPU processing, thus, it would be better to rephrase this as \"For efficient batch processing, architectures such as....\"\n \n- The paper mentions \"We believe after the mixing, elements at every position summarize good information from all input positions.\". While at the end of $log(N)$ steps, each output token receives information from each input token, the mixing doesn't seem uniform. For instance, consider the case of $i$-th token. Tokens $i+1$ and $i+2$ would mix with it in a single step. In the next hop/block $i+1$ token would again mix with $i+2$ token carrying information received from $i$-th token. In contrast, $\\exists$ a token that mixes with the $i$-th token only at the last hop. Could it affect the performance or introduce inductive biases? It would be good to discuss this case. Note that the paper covers reaching probabilities in Appendix, however, I am not sure if that answers the question completely. \n\n- The paper says \"A ChordMixer network consists of $log(N_{\\text{max}})$ blocks, where $N_{\\text{max}}$ is the length of the longest sequence.\" Does each input get processed with the same number of blocks or do you use fewer blocks for shorter sequences? Another question is what happens if you obtain a sequence of length $2 \\times N_{\\text{max}}$ during inference? Though this may not be likely for datasets with long sequences.             ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5D5Z4QYZfT", "reviewer": "Reviewer_Bvdo", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, the authors propose ChordMixer: a simple neural network building block that is able to mix tokens within a sequence. Each ChordMixer block consists of a rotation layer followed by 2-layer MLP. Compared to previous methods, ChordMixer allows attention over variable input length and performs favourably on very long sequence tasks. The authors show results on three toy tasks: synthetic addition problem, long document classification and DNA sequence-based taxonomy.\n\n======== Post-rebuttal update ========\n\nAfter reading other reviewers' comments and the authors' rebuttal, I decided to upgrade my score to \"8: accept, good paper\". The model is simple and clever and the experimental results are convincing. Hopefully the code will be available. Congratulations!", "summary_of_the_review": "Based on the comments above, I am rating this paper as \"marginally above acceptance threshold\". The mode is simple, somewhat novel and they show better results than current models on toy datasets with very long sequence lengths. It would be nice if the authors could clarify the points I mentioned on the \"weaknesses\" section.", "strength_and_weaknesses": "### Strengths\n- The paper is well written and easy to follow. The authors did a good job on related works and provide a clear explanation of the proposed model.\n- The problem tackled on this paper—modelling attention in very large sequences—is of extreme practical importance in many fields of machine learning.\n- The proposed idea is very simple and intuitive. With a relatively simple and straightforward approach based on a P2P protocol, the authors are able to overcome some issues of current methods (eg, variable length and good performance in very long sequences).\n\n### Weaknesses\n- The paper only show results on very toysh tasks. Although I understand that even though standard models fail on those tasks, it would be much more interesting to see results in more realistic tasks (and/or on unsupervised pre-training).\n- It is unclear to me why some models appears in the evaluation of some tasks, but not others. Eg, S4, Luna appear on the “Adding problem” but not on others and the “long document classification” only has 4 models. ow does the omitted models perform on those tasks? are they comparable or better than ChordMixer?\n- As pointed by the authors, this approach also uses the Chord protocol. However, Paramixer does not show on any experimental comparison. It would be nice to compare ChordMixer and Paramixer model, in particular what are the pros and cons of each architecture.\n- As mentioned by the authors, training requires that every batch contains sequences of the same length. Is this an issue? Can this bias the model in some particular way?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster