Orchid: Flexible and Data-Dependent Convolution for Sequence Modeling
Authors: Mahdi Karami
Ali Ghodsi
Venue: NeurIPS 2024 poster (2024)
Keywords: Transformer
Long Convolution
BERT
LLM
Input-dependent filter
Primary area: deep_learning_architectures
TL;DR: This paper introduces Orchid, a new deep learning architecture that replaces computationally expensive attention mechanisms with a more efficient and scalable input-dependent convolution-based approach.

Abstract: In the rapidly evolving field of deep learning, the demand for models that are both expressive and computationally efficient has never been more critical. This paper introduces Orchid, a novel architecture designed to address the quadratic complexity of traditional attention mechanisms without compromising the ability to capture long-range dependencies and in-context learning. At the core of this architecture lies a new data-dependent global convolution layer, which contextually adapts its kernel conditioned on input sequence using a dedicated conditioning neural network.  We design two simple conditioning networks that maintain shift equivariance in our data-dependent convolution operation. The dynamic nature of the proposed convolution kernel grants Orchid high expressivity while maintaining quasilinear scalability for long sequences. We evaluate the proposed model across multiple domains, including language modeling and image classification, to highlight its performance and generality. Our experiments demonstrate that this architecture not only outperforms traditional attention-based architectures such as BERT and Vision Transformers with smaller model sizes, but also extends the feasible sequence length beyond the limitations of the dense attention layers. This achievement represents a significant step towards more efficient and scalable deep learning models for sequence modeling.

Orchid: Flexible and Data-Dependent Convolution for Sequence Modeling
Mahdi Karami Google Research mahdika@google.c com
Ali Ghodsi
School of Computer Science
University of Waterloo, ON, Canada ali ghodsi @uwaterloo.c
Abstract
In the rapidly evolving field of deep learning, the demand for models that are both expressive and computationally efficient has never been more critical. This paper introduces Orchid, novel architecture designed to address the quadratic com- plexity of traditional attention mechanisms without compromising the ability to capture long-range dependencies and in-context learning. At the core of this ar- chitecture lies a new data-dependent global convolution layer, which contextually adapts its kernel conditioned input sequence using dedicated conditioning neural network. We design two simple conditioning networks that maintain shift equivariance in our data-dependent convolution operation. The dynamic nature of the proposed convolution kernel grants Orchid high expressivity while maintain- ing quasilinear scalability for long sequences. We evaluate the proposed model across multiple domains, including language modeling and image classification, highlight its performance and generality. Our experiments demonstrate that this architecture not only outperforms traditional attention-basse architectures such as BERT and Vision Transformers with smaller model sizes, but also extends the feasible sequence length beyond the limitations of the dense attention layers. This achievement represents significant step towards more efficient and scalable deep learning models for sequence modeling.
Introduction
In modern deep neural networks, attention mechanisms have emerged as a gold standard, pivotal in domains such as natural language processing, image, and audio processing, and even complex fields like biology |Vaswani et al. 2017 Dosovitskiy et al. 2020 Dwivedi and Bresson 2020) However, despite their strong sequence analysis capabilities, these sequence modeling mechanisms suffer from their high computational complexity, which scales quadratically with sequence length, hindering their application to long-contens tasks. This complexity has driven a shift towards innova- tive solutions to overcome this computational barrier, enabling analysis of long sequences in areas like genomics, DNA sequencing, and the creation long musical compositions.
In the past years, researchers have explored various strategies to tackle the computational bottleneck of traditional dense attention layers (Tay et al.] 2022). One key strategy involves sparsifying the dense attention matrix. Instead of calculating the entire matrix. Qiu et al. [2019), Parmar et al. (2018) focus on specific local blocks of the receptive fields of sequences by chunking them into fixed-size blocks. Moreover, Sparse Transformer [Child et al.) 2019]. Longformer [Beltagy et al.] 2020 and BigBird [Zaheer et al., 2020) use strided attention patterns combined with local sliding windows to reduce computation. In contrast to using pre-determined patterns, other techniques include learn- ing to cluster/sort tokens based on a similarity function, thereby enhancing the global view of the sequence, as seen in Reformer [Kitaev et al. 2020 Routing Transformer [Roy al. 2020 Sparse
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Sinkhorn attention [Ty et al. 2020]. Another approach involves low-rank approximations of the self-attention matrix, leveraging the insight that these matrices often exhibit low-rank properties, as demonstrated by Linformer [Wang et al. (020) which projects keys and values matrices to lower- dimensional representation matrices. Another paradigm to reduce quadratic computation cost, is to replace the dot-product similarity between keys and query matrices of attention mechanism with a kernel function and avoid explicitly computing the attention matrix [Katharopoulos et al. 2020]. Notable examples in this family include Performers [Choromanski et al. 2020], Random Feature Attention [Peng et al., 2021] that are based on random feature approximation of the kernel function. Additionally, some models leverage combinations of such techniques to design efficient trans- former (Zhu et al. 2021 Zhang et al., 2021]. However, while these methods significantly reduce computational overhead, they may sacrifice expressiveness and performance. often requiring hybrid approaches that combine them with dense attention layers [Mehta et al. 2022 Fu et al. 2023 On the other hand, recent works have aimed at sparsifying dense linear layers, used for feature mixing in Transformer blocks, to tackle another major source of high computation and memory demand in large models [Dao et al.) 2022 Chen al. [022T]
Finding sub-quadratic and hardware-efficient mixing operators that are also expressive remains a significant challenge. Recent studies have explored attention-free solutions, particularly using state
space models (SSMs) Gu et al. 2021 Mehta et al. 2022, Wang et al.) 2022 Fu et al. 2023 Orvieto
et aL.
2023 Gu and Dao 2023 De al. 2024], and long convolutions [Romero et al. 202 Li et al. terms of its internal state using state equation, describing the dynamics of the system using first-order differential equations over the states, and an observation equation, relating state variables to observed outputs A key insight is that, most of these SSM models can be formulated as a long convolution model between the input and output sequences [Gu et al.) 2021). allowing parallel and efficient training. However, recent work by Poli al. [2023] demonstrated that directly parameter- izing the filter impulse response of the long-convolution leads to an even more expressive sequence mixing layer.
2022. Poli et 2023).
state space model characterizes a dynamical system's 's behavior
This paper proposes a novel data-dependent convolution mechanism to tackle the inherent quadratic complexity of traditional attention mechanisms, while maintaining the model's ability capture long-range dependencies and in-context learning. The data-dependent convolution layer contextu- ally adapts its kernel based input data using a dedicated conditioning neural network. We design two simple yet effective conditioning networks that maintain shift equivariance in the adaptive con- volution operation. By combining these adaptive mechanisms with gating operations, our proposed model-named Orchid-achieves high expressivity while offering quasilinear scalability (with a complexity of (L log L)) for long sequences. Evaluation across various domains, including lan- guage modeling and image classification, presented in section + and Appendix, demonstrates the Orchid architecture's 's performance and generality, outperforming attention-based architectures, like BERT and Vision Transformers, with smaller model sizes. Moreover, its allows for handling very large sequence lengths that are beyond the limitations of the dense attention layers. This achieve- ment lays the foundation for further ad advancements in more efficient and scalable sequence modeling architectures.
2 Background
Self-Attention Mechanism: Given a length-L sequence of embeddings (tokens) æ (I1, (f1,22, .2. #L), the self-attention layer generates a new sequence by computing weighted sum of these embeddings. To achieve this, it linearly project x into three components: queries (Q), keys (K), and values (V), as: Q = xWQ K æW V wV Each individual atten- tion mechanism within a multi-head self-attention layer operates as a dense linear transformation, expressed as:
QK" Vdz
y = SSA(Q K, V)- = -SffMMax
V = A(x)V,
where the matrix A(x) contains the normalized attention scores between each pair of tokens. This description of the attention layer highlights its notable benefits, including its capability to capture
Notably, state space models, in general, include the recurrent layers such as RNN and LSTM Hoccreiter al. 1997 special cases.

---

hg (2)
ngg (a)
Conv1D
Conv1D
Conv1D
MLP
Conv1D
Conv1D
ConviD
k2((3)
Figure 2.1: Orchid block architecture. This diagram illustrates the structure of the Orchid block. The core operation is convolution (denoted by efficiently implemented the frequency domain using FFT. Element- wise multiplication is denoted by O. On right side, two different conditioning networks, introduced in equations ( and (3) as shift-invariant convolution kernels, are illustrated. In this model, the convolution performed efficiently in the spectral domain, so the kernel in the frequency domain, h² = Ag hg (æ). computed. The block also includes MIPS for linear projection and pointwise mixing of features at the beginning, that common design choice used in various sequence modeling architectures.
long-range dependencies using sublinear parameter count. The attention mechanism enables di- rect computation of interactions between any two positions in the input sequence, regardless their distance, without a corresponding rise in parameter counts. Additionally, the attention layer imple- ments a data- deteeddenndn dense linear filter, which effectively filter the input based on on weights conditioned by mapping of the data. This property makes it expressive and flexible enough to en- code a large family of linear functions. However, these advantages come at the expense of quadratic computational complexity and memory costs.
This motivates develop efficient and scalable data-dependent convolution mechanism, fea- turing an adaptive kernel that adjusts based on the input data. The kernel size of this convolution layer long the input sequence length, enabling the capture of long-range dependencies across the input sequence while maintaining high scalability.
Discrete-time linear convolution is fundamental operation in digital signal processing that calculates the output as the weighted sum of the finite-length input æ with shifted versions of the convolution kernel, h, also known the impulse response of linear time-invariant (LTI) system Formally, it can be written as
Linear Convolution:
L-1 Σ hlt Ex1 Em
i = (h * xt
In this definition, the output is a linear filter of the zero-padded input and convolution kernel. How- ever, other padding schemes leads to different forms of convolution. A well-known form is circular convolution, defined as
L-1 hit - mod L]
y mod L] = (h @ >){f &
Σ
which is equivalent to the linear convolution of two sequences if one is cyclically padded at its edges.
Global Convolution and Fast Convolution Algorithm: Standard convolution layers, explic- itly parameterized with a short kernel, struggle to capture long-range dependencies in sequential data. Extending the kernel match the input length enables modeling such dependencies but leads to linear growth in parameter counts and quadratic computational complexity. To mitigate the parameter growth challenge, the kernel of global (a.k.a. long) convolution can be implicitly
While generally represents sequence of D-dimensional embeddings with length L, all the sequence mixing operators, including data-dependent convolutions, Fourier transforms depthwise ID convolutions (Convid) are performed along the sequence dimension. Therefore, for clarity and without loss of generality, we assume D = 1 and E R² 4 For full list of notation definition, please refer to Appendix A

---

parameterized using a multilayer perceptron (MLP). technique that has been shown to main- tain sub-linear parameter scaling [Karami et al., 2019 Romero et al.) 2021 Li al.) 2022 Poli et al. 2023]. Furthermore, a key advantage of convolution operators is that, leveraging the con- volution theorem, convolution operators can be efficiently computed the frequency domain us- ing Fast Fourier Transform (FFT) algorithms, thereby reducing the computational complexity to (L L) [Cooley and Tukey 1965 Formally, the linear convolution can be expressed in the frequency domain as y F (F-((F()) @ F(t)) Th & T where T is the DFT matrix, F denotes the discrete Fourier transformation, and # denotes the zero-padded signal, defined as Φ padyy (x) [0z: a=. Additionally, the circular convolution can be simply computed
h ① x = F F- (F(h) o F(x)).
3 Orchid Operator
This section introduces the Data-Dependent Convolution Filter, novel operator aimed at increasing the expressiveness of long convolution operations. This operator serves as the foundational building block for the Orchid layer, which we will explore later in the section.
3.1 Data-Dependent Convolution Filter
We hypothesize that making the convolutional kernel data- lata-dependent allows the filter to adapt the specific characteristics of its input, potentially capturing more complex patterns within the sequence. Formally, this input-dependent filter is defined as:
ho x: NNo (ar)
(1)
The key innovation to replace the static convolutional kernel with a conditionally generated one controlled by the input data. This is achieved through conditioning network, denoted as ho(x) = (N) neural network parameterized by 0. The conditioning network outputs a vector matching the input sequence in length. This allows each input token to 'attend' to the entire sequence with personalized, adaptive weights derived from specific representation. Convolving the surrounding context using this data-dependent weighting scheme can potentially offer more effective sequence mixing compared to conventional static convolutions.
3.2 Preserving Shift- Eufiv--quiiari in Data-Dependent Convolution
fundamental property of discrete convolution is shift equivariance, meaning that shifting the input by certain amount leads to corresponding shift in the output (disregarding boundary effects). This is formally expressed for circular convolution as: shift,, (y) = @ shift,,. (x) [Bronstein et al., 202T], where this property holds exactly regardless of boundary conditions. The shift operation is defined as shift,, [t] A zl( + m).
This property particularly important because it ensures the operator's response robust to shift of features within the input, thereby enhancing the model's generalization capabilities. This inductive bias at the core of the widespread success of convolution operations [Thomas et al.). Therefore, it is desirable to design conditioning network in the data-dependent convolution (1) to preserve shift equivariance property. To maintain this property for data-dependent convolution operations, it is sufficient to design filter kernel to be shift-inarrintt, i.e. h(shiftm (x)) h(æ)) (refer to Appendix for the proof). the following, we present two conditioning network designs satisfying shift-
invariance.
Phase Suppression for Shift Invariance: cireular shift of sequence results in a lin- ear phase shift of its frequency components: ([)s = u u²(w] e 22 wm (Oppen- heim 1999]. Given a shift-equivariant function g(x) (such depthwise Convid()) (satisfying: o(shift, (x)) shift,, =hift,,(g(z)) (g(x))). Its frequency components after spatial shift of its input main- tain this phase shift:
F(g(shiftm (x)) = (g(xx) [w] 1
By taking the magnitude (absolute value or squared) of these complex-valued frequency compo- nents, we effectively eliminate the phase shift, therefore, defining ht (xx) F(((x)) satisfies shift-invariance property: he (shiffmmmmm (x)) h (xx)

---

In our design, we deploy a hybrid consists of ID depthwise linear convolution (Convid()) with short kernel length (typically 3-5) acting at the spatial domain, followed by short convolution in the frequency domain. By operat- ing in both spatial and frequency domains, the conditioning network effectively mixes information from neighboring tokens and spectral components. The resulting conditioning neural network is formulated as:
domain conditioning network. This network
hg (a:) Convid (Convid(a:)) I)
This architecture choice aims to mínimize the number of parameters and computational overhead introduced by the conditioning network within the overall model.
II) Leveraging Cross-Correlation for Shift-Invariance: An alternative approach to achieving shift-invariance involves computing the cross-correlation between two mapping of the input quence. Let k(x) and ((x) be two shift-equivariant functions, satisfying: k(shiftm (x)) - shiftm (k(x)) and (shiffm (x)) shiftm(g(z) (g(x)) We define h(x) as the cross-correlation
of k(x) and g(x), given by:
h(x)(t] (k(x)) (t)))
Σ k()] ((x)[t + mod LJ.
This operation essentially slides ((r)) over k(x) and measures their similarity at different offsets. Remarkably, the resulting cross-correlation function, l((z), is also shift invariant:
h(shiftm (x)) = (sshiftm())) ((hhift (x))
shift,, (A(x)) shiftm (1(=))
k(xz) * ((x) = l(()))
Furthermore, the convolution theorem enables efficient computation of the cross-correlation in the frequeney domain: (x) F (k(x) * ((x)) = h-th (x) @ (x(x) where kf denotes the complex conjugate of k- and 3 represents element- multiplication.
Remark 3.1. By setting k(x) (()) g(x). obtain (==)x=) (x))2 This indicates that the cross-correlation approach generalizes the magnitude-bant approach, demonstrating its versatility.
Similar to the previous approach, we employ separate 1D depth-wise short convolutions for both k(x) and (x),, followed by another convolution post cross-correlation in the frequency domain. As result, the conditioning neural network is defined as
hg (x) Convid [F* (Convid(()) O F (Convid(x))).
(3)
Both conditioning functions, as defined in and are illustrated schematically in Figure 2.1
Remark 3.2. For convolution operations, augment the data-dependent conditioning network by incorporating a fixed (static) term. This term adds positional encoding to the convolution kernel by implicitly parametrizing it using positional embedding, PosEmb(), of time step (token index in the sequence) and a feed forward networks as hn = FFN (PosEmb(()) [Romero et al. 2021 Li et al, 2022 Poli et al. 2023 The final convolution kernel is obtained by summing this positional bias with the output of the conditioning network, h = (x:) + ho-
Remark 3.3 Dataa-Depnddent Convolution as Cross-atiention Alternative). The kernel of con- volution (x), defined in equations ? or (3). is conditioned on the input of the convolution layer, making it input-dependent However, we can generalize this concept further. The kernel could be function of any arbitrary sequence u, leading to broader definition of data-dependent convolution:
(x, u) = he u) x NNo(u) x
This definition couples the input sequence with another sequence u. creating a potential alternative to cross-attention layers in sequence processing tasks. We therefore refer to the proposed layer as dlata-dependentt in more general sense. When dealing with sequences of different lengths, the shorter sequence can be zero- aroopp to match the length of the longer one. Specifically, assuming E R is longer than u E R (L > N), we use the zero-padded sequence = pady(u) E R as input to the conditioning network NNo(ū). Since the long convolution is implemented in the frequency domain, this zero-paddin parddpg in the time domain translates to interpolation in the frequency domain (mmith 2008 ensuring that both sequences have frequency components of the same length.
5

---

3.3
Orchid Block
Unlike attention layers, convolution filters leverage parameter sharing. This means they slide the same kernel weights and apply them to different positions within the input sequence. Mathemati- cally, this operation is equivalent to multiplying an input vector with a structured matrix, such as a Toeplitz matrix for linear convolutions or a circulant matrix for circular convolutions, which results in computational efficiency [Gray et al. 2006, Karami et al. 2019]. To achieve leeationddependet filtering scheme, we complement the data-dependen convolution with element-wise multiplications, allowing the model to emphasize specific tokens within by assigning higher weights prior to apply- ing the location-invarian
convolution. Notably, prior research has demonstrated that a cascade of circulant and diagonal matrices can effectively approximate dense linear layers [Moczulski et al. 2013 Cheng et al., 2013). Building upon these insights, the overall architecture of the Orchid block, is composed of a chain of M data-dependent convolution and element-wise multiplications (gated connections). In our experiments, we utilize simple chain of order 1.5, consisting of data- dependent convolution sandwiched by two element-wise multiplications: y = (fz a S. o (x) where denotes composition, [a) (ho(#) + ho) and f (æ) A Convid(æ)) o The Orchid
block illustrated in Figure 2.1 and its basic implementation is presented in appendix D
Overall Computational complexity. All global convolutions within the Orchid block are computed in the frequency domain using FFT algorithm, inheriting its computational efficiency with complex- ity of Oo L). Furthermore, the element-wise multiplications contribute an additional O(L) complexity. Consequently, the overall complexity of the Orchid block scales guasi-linearly with the sequence length, resulting in a total complexity of O L), where M is the number of layers in the block. A recent hardware and I/O optimized implementation of FFT, introduced in [Fu et al. 2023), can speed up the overall computation of Orchid on modern accelerators. Empirical runtime comparisons against standard attention mechanisms, detailed in Appendix C.5) highlight its expected scalability, especially for longer sequences.
4 Experiments
Our evaluation of Orchid focuses on three different Transformer-based models to evaluate its ex- pressivity and generalization capabilities as an alternative to attention layers. Firstly, we conduct a set of experiments on a synthetic task to assess the in-context learning ability and scalability of the proposed model. Subsequently, we evaluate the performance of the proposed architecture on language modeling tasks. Moreover, we extend our experiments to image classification tasks, aim- ing to evaluate the model's generalizability across diverse domains. Additional ablation studies on model architecture and also an experiments on raw speech classification with long sequences are presented in Appendices C.3 and C.2 Unless otherwise specified, our experiments adopt the phase supersession (Type I) conditioning network (Equation [ due to its simpler form. For an overview experimental details, please refer to Appendix C
4.1 Synthetic In-context Learning
The aim of the first experiment is to assess how well our model performs on a synthetic reasoning task. This task, inspired by prior work on language model benchmarking [Liang et al.) [022] and in-context learning (ICL) [Garg et al.) 2022), is known as Associative Recall. It involves generating value from key given a string of key-value tuples from a random dictionary. For instance, given the input ([a, 1, b, e, f, 3), b), the model is expected to return e, the value associated with the key b. This task assesses whether model can effectively retrieve the correct value from key in a prompt, essentially applying a data-controlled shift. Attention mechanisms offer this capability by computing attention scores through token comparisons and then weighting the entire sequence accordingly [Olsson et al., 2022]. Associative recall has been pivotal in guiding the design of long convolution models, as demonstrated in (Fu et al. 2023 and more complex variant of this task was employed in [Poli et al. 2023
For these experiments, we benchmark Orchid against several leading long convolution models, including: 1) H3, which utilizes state-space models (SSMs) for implicit parametrization of long convolution, as proposed in [Fu et al.) 2023). II) CKConv, that employs feedforward networks (FFNs) and positional embeddings for the implicit parametrization of convolution operations, de- tailed in [Romero et al. 2021]. III) Hyena, built upon the CKConv framework by incorporating an

---

The performance (test accuracy) of in-context learning on the associative recall task with different sequence lengths and vocabulary size of 20, The results for the baseline models are drawn from Poli et al. 2023). Fu et al. [2023]. The symbol x indicates that the Transformer model failed to complete the task within a week the model does fit in memory.
Table 4.1:
Table 4.2: The test accuracy of the associative recall task with varying vo- cabulary sizes and a sequence length of 128.
Model
20
40
Model 128
512
2K
8K
32K
128K
Transformer
100
100
100
CKConv
91
25.7
20.4
Transformer
100
100
100
100
X
X
H3
71.5
13.2
10.2
Monarch Mixer
98.7
99.4
99.4
99.4
99.4
Hyena
93
38.8
12.4
Hyena
93
99
99.6
100
100
Mamba
100
100
35.8
Orchid
100
100
100
100
100
100
Orchid
100
99.4
99.2
Vocabulary Size = 20
Vocabulary Size= 30
Vocabulary Size = 40
100
80
60
Orchid
40
CKConv
H3
20
Hyena
0
2
2
2 Sequence Length
213
2
27
2
22
228
2
27
2
2
213
2
Sequence Length
Sequence Length
Figure 4.1: Test accuracy of the associative recall task across different long implicit convolution models on various soquence lengths and vocabulary sizes (number of possible token values).
additional exponential decay modulation into the implicit convolution process, as detailed in [Poli et al. 2023]. It is further augmented by multiplication in a chain of order 2.
As illustrated in Figure 4.1 and Tables and 4.2 Orchid demonstrates superior expressiveness and outperforms existing long convolution models in associative recall tasks. These tasks become in- creasingly challenging with shorter sequences and larger vocabulary sizes. This difficulty arises be- cause specific (key, value) pairs appear less frequently within shorter strings, hindering the model's ability to learn and reason on these associations. Remarkably, in such challenging scenarios with short sequence lengths of 128 and large vocabulary sizes, Orchid significantly improves the model's accuracy and closes the gap between Transformer and implicit convolution models. Furthermore, Orchid successfully learns the task even with extended sequence lengths of up to 131K tokens, scale at which Transformer models encounter computational difficulties, which highlights Orchid's superior scalability and efficiency in learning long context.
The insights from this experiment guide us in integrating the proposed model into Transformer- based models for extensive language modeling, suggesting its potential to enhance performance in natural language processing tasks.
4.2 Language Modeling
We evaluate the Orchid layer in language models. Orchid is designed to integrate seamlessly with existing BERT-style language models, such as BERT [Devlin et al. 2018), RoBERTa [Liu et al. 2019). SpanBERT (Johh et al., 2020). and others [Jin et al., 2020). In our experiments, replace the attention layers in the standard BERT framework in [Devlin et al. 2018) with Orchid layers. For each Transformer block in the BERT-style model, we replace the attention layers with Orchid layers for sequence mixing. We also replace the two dense matrices in the MLP layers, used for dimension mixing in Transformers, with block-diagone matrices (Dao et al. 2022 Following (Fu et al. 2023), we add a residual long convolution to each Orchid layer.
Our BERT-style model, called Orchid-BERT-base has 12 layers with hidden size of 768, the same dimension and depth as BERT-base. The resulting Orchid-BERR BEdd---RR-base have 77M parameters, com- pared to BERT-base's s 10M parameters. We also pretrain
of 254M parameters
7

---

Table 4.3: Average GLUE Score of BERT-base and BERT-large BERT-base and Orchid BERT base, and A2--BERT-base and M2 BERT-ERTaaggg Dao et al. 2022 Baseline results are drawn from Fu et al. 2023).
Devlin al. 2018 in comparison Orchid-
Model (size)
GLUE Score
A Params
A GLUE Score
BERT-base (110M)
79.6
M2-BERT-base (80M)
79.9
-27.3%
+0.3
Orchid-BEae BERT-base (77M)
80.6
-30.0%
+1.0
BERT-large (340M)
82.1
M2-BERT-large (260M)
82.2
-23.6%
+0.1
Orchid-BERT BaRT-large (254M)
82.7
-25.3%
+0.6
with hidden dimensions of 1536 and 12 layers. Orchid models are pre-trained using masked lan- tokenizer.
guage modeling over the C4 dataset [Raffel et al. 2019 with the
Finetuning Performance on GLUE Benchmark. We conducted an evaluation of Orchid-BERY models GLUE fine-tuning tasks, comparing them against the baseline models: BERT-base and BERT-large, and the recent long convolution-basse models: M2-BERT-base and M2-BERT- large [Fu al. [023]] The fine-tuning process executed in accordance with the methodology described by| Izsak et al. [2021]. As the results outlined ablle/.3]show Orchid-BERO
is able to achieve 1.0 points improvement in average GLUE score performance compared to the BERT-base out- performs the performance of BERT-large by .6 points with 25% reduction in parameter counts.
on the GLUE benchmark with utilizing 30% fewer parameters. Similarly,
4.3 Image Classification
We extend the application of Orchid to the Vision Transformer (ViT) architecture, introduced by Dosovitskiy et al.) (2020), by replacing its attention mechanism with Orchid similar to language modeling task. Similar to language modeling task, we substitute the dense matrices in the MLP lay- ers, which perform dimension mixing, with block-diagonal matrices and incorporate a residual long convolution within each Orchid block. We benchmark
model against recent long convolution- based models, specifically Hyena- ViT-b Poli et al. 2023) and M2-ViT-b Fu et al. 2023].
Models are evaluated for image classification two widely used image datasets: CIFAR-10 10 and ImageNet-1K. K. For CIFAR-10, images are transformed into sequences 4 x pixel patches and processed using ViT architecture composed of 6 Transformer layers with hidden sizes of either 128 and 220 for Orchid-s and Orchid-m, respectively. In the case of ImageNet- K, we segmented images into patches of 16x x 16 pixels, and we trained ViT-base architecture featuring 12 Transformer layers and hidden size of 768.
The results presented in Table and demonstrate that Orchid significantly outperforms both the Vision Transformer baseline and long convolution- based models on the CIFAR-10 10 and ImageNet- IK datasets. Notably, Table 4.5 shows that utilizing smaller image patches, which lead to longer sequences, can further enhance performance. This observation underscores the advantage of scalable sequence models like Orchid. These results confirm the generalizability and effectiveness of the Orchid architecture beyond the domain of language modeling, highlighting its potential advantage in broader range of applications such image processing tasks.
Related Work
Previous works have explored various forms of dynamic convolution architectures [Wu et al. 2019
Karami et al. 2019 Chen al. 2020 Jiang al., 2020]. The dynamic convolution Wu al.
2019 utilizes short convolution kernel that depends solely on the current time-step, whereas Jiang
al. 2020) expands the kernel span to depend on local window. Meanwhile, Chen al.) [2020] modeled the convolution kernel as mixture of short convolution kernels with mixture weights controlled by average pooling of the input embedding. However, the reliance on short convolutions and their specific kernel modeling approaches limits their ability to capture long-range dependencies
and scaling their kernel to match the sequence length computationally impractical. In a different
line of research, Fourier Neural Operator (FNO) [Li et al. 2020 and adaptive FNO (Guibas et al.)

---

Table 4.4:
Performance comparison of Orchid with ViT-based models ImageNet-1k. Baseline results
drawn from Fu 2023
Model (size)
Top-1 (%)
Top-5 (%)
ImageNet-Ik Ik
ViT-b (87M)
78.5
93.6
ViT-b+Monarch (33M)
78.9
94.2
Hyena-ViTas (88M)
78.5
93.6
M2-ViT-h (45M)
79.5
94.5
Orchid (48M)
80.2
94.9
Table 4.5: Performance comparison of Orchid with ViT-based models on CIFAR-10 dataset. Orchid's perfor- mance is also evaluated over different patch sizes, x 4, x and x pixels. Orchid-s and Orchid-m refers to the ViT architecture composed of layers with hidden sizes of 128 and 220, respectively.
(Type II) conditioning network (equation 3) is identified with -ce and the rest are using type I (equation 2 Baseline results are drawn from [uu et
2023 and [Knigge
2023
Model (sizc) Top-1(%)
Model (size) Top- (%)
Model (size) Top-
CIFAR-IO (4 x 4)
CIFAR-IO (1 x L)
CIFAR-10 (2 x 2)
VIT (1.2M)
78,6
CKCony (1M)
63.74
Orchid-s (790K)
92.2
Mrn+Monarch (607K)
79.0
S4 (7.8M)
91.13
Orchid-s-ce (799K)
92.3
Hye (1.3M)
80.6
M2-VIT (741K)
91.0
Orchid-m (2.1M)
93.33
M2-VIT (741K)
80.8
CCNN (2M)
93.08
Orchid-s (735K)
88.5
Orchid-m (2M)
93.0
202
operate in the spectral domain, applying dense linear layer an MLP with a block diagonal linear layer. However, these models not explicitly model convolution kernel and do not enforce shift-equivariance.
Recent advances in input-dependent state space models (SSMs) have shown promise in efficient sequence modeling by allowing model parameters to dynamically adapt based on the input Gu and Dao 2023 However, the input-dependent mechanisms these models typically rely on the current token or its local neighbors, preventing them from leveraging the benefits of global con- volution for efficient parallelizable training Consequently, they heavily depend on hardware-awe aware implementations optimized for modern GPUs. While effective in certain tasks, these models have been shown to struggle with recall-intensive scenarios [Arora et al. 2024). In contrast, our pro- posed data-dependent global convolution allows the conditioning network to be influenced by the entire input context, enabling efficient sequence mixing. Moreover, the current formulation of input- dependent SSMs is not readily adaptable for efficient cross-attention between sequence pairs. This highlights a promising future direction for research: exploring how the complementary strengths of data-dependent global convolutions and input-dependent SSMs can be combined to develop foun- dation models that excel across a broader range of tasks.
Recent studies have explored sub-quadratic sequence mixing methods using long convolutions or state space models, leveraging the fast convolution algorithm for computational efficiency. While utilizing Fast Fourier transform results in O log I.) computational complexity. FFT algorithms exhibit suboptimal hardware utilization and suffer from slow I/O between layers of the memory hierarchy on modern GPUs due to their sequential nature. To address this bottleneck, FlashFFT Conv [uu et al., 2023) utilizes a matrix decomposition to leverage matrix multiply units and enable kernel fusion resulting in a more hardware and I/O efficient implementation of long convolutions. Moreover, the Monarch Mixer (M2) [Fu et al. 2023], offers an expressive family sub-quadratic structured matrices that generalizes the DFT and other structures. These matrices parame- terized as products of block-diagone matrices, offering sub-quadratic computation costs ranging from (Llog T.) (T,3/2). By trading-off computational complexity with FLOP utilization, M2 achieves a hardware-efficien alternative for Transformers.

---

Discussion and Conclusion
In conclusion, work introduces Orchid, novel model that addresses critical challenges of efficiency and scalability in sequence modeling through the innovative use of data-dependent con- volution. Orchid successfully mitigates the quadratic computational and memory costs associated with attention layers, while retaining, and in many cases enhancing, the model performance across different domains. The introduction of data-dependent convolution layer represents significant step forward, offering a scalable and expressive alternative sequence mixing scheme that adapts its weights the input data. Through evaluation across multiple domains, including in-context learn- ing, language and image processing tasks, Orchid has demonstrated not only its superior perfor- mance over traditional attention-based models but also its generality and scalability. This positions the Orchid model not just as alternative to existing paradigms but potential catalyst for innova- tion, driving the exploration of novel, efficient, and powerful architectures in artificial intelligence.
The superior performance of Orchid compared to traditional transformer- bhased models raises in- triguing questions about the current state and future direction of deep learning architectures. One plausible explanation for our model's effectiveness could be the werrparameteerizttion prevalent in transformer-basee models. A growing body of evidence indicates that attention mechanisms, despite their computational complexity, utilize only fraction of their capabilities for tasks like language processing. This challenges the common belief that attention is the key ingredient for large-scale deep learning, leading us to reconsider its role and seek more computationally efficient alternatives.
Limitations and Future Directions
Looking ahead, extending our model accommodate causal models, particularly for autoregressive language models akin to GPT, is an intriguing future direction. The current form of the proposed model is not inherently compatible with these architectures, primarily due differences in how data-dependent global convolution handle dependencies and sequence generation
Furthermore, exploring the capability of Orchid efficient alternative to cross-altention layer, employed in open up new possibilities for integrating our model into more advanced foundation models and cross-domain applications.
models, offers another avenue for research. These considerations
Beyond sequence modeling, the Orchid block, with its input-dependent long convolution, local depthwise linear convolution (Convid), and dlement-wise multiplications, inherently extendable to muuli--iimensione data. While the primary focus of this work designing efficient and scal- able architecture specifically for sequence modeling, expanding the proposed architecture to include 2D or 3D long convolutional approaches is an interesting future direction.
'Notably, recent works such Ding et al. 2023 Bachmann and Nagarajan 2024 show that auto- regressive models not optimal for inference in language models.
10

---

References
[1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. volume 30, 2017.
[2] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. /1929, 1929, 2020.
[3] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. arXiv preprint arXiv:2012.09699, 2020.
[4] Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey. ACM Computing Surveys, 55(6): 2022.
[5] Jiezhong Qiu, Hao Ma, Omer Levy, Scott Wen-tau Yih, Sinong Wang, and Jie Tang. Blockwise self-attention for long document understanding. arXiv preprint wrXiv:191..029777 2019.
[6] Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, tukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. Proceedings of ICMI. 2018, 2018.
[7] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint arXiv:1904. 10509, 2019.
[8] Iz Beltagy, Matthew Peters, and Arman Cohan. Longformer: The long-document trans- former. arXiv preprint arXiv:2004.05/500 2020.
[9] Manzil Zaheer, Guru Guruganesh, Avinava Dubey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transformers for longer sequences. Proceedings of NeurlPS, 2020.
[10] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference on Learning Representations, 2020.
[11] Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-based sparse attention with routing transformers. Proceedings of TACL, 2020.
[12] Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. Sparse sinkhorn attention. Proceedings of ICML, 2020.
[13] Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self- attention with linear complexity. arXiv preprint arXiv:2006.04776 2020.
[14] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Flcuret. Transformers mns: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning, pages 5156-5165. PMLR, 2020.
[15] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009. 14794, 2020.
[16] Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah A Smith, and Lingpeng Kong. Random feature attention. Proceedings of ICLR, 2021.
[17] Chen Zhu, Wei Ping, Chaowei Xiao, Mohammad Shoeybi, Tom Goldstein, Anima Anandku- mar, and Bryan Catanzaro. Long-short transformer: Efficient transformers for language and vision. Advances in Neural Information Processing Systems, 34:17723-17736, 2021.
[18] Hang Zhang, Yeyun Gong, Yelong Shen, Weisheng Li, Jiancheng Lv, Nan Duan, and Weizhu Chen. Poolingformer: Long document modeling with pooling attention. Proceedings of ICMI, 2021.
[19] Harsh Mehta, Ankit Gupta, Ashok Cutkosky, and Behnam Neyshabur. Long range language modeling via gated state spaces. arXiv preprint arXiv:2206. /3947, 2022.

---

[20] Daniel Y Fu, Tri Dao, Khaled K Saab, Armin W Thomas, Atri Rudra, and Christopher Ré. Hungry hungry hippos: Towards language modeling with state space models. International Conference on Learning Representations, 2023.
[21] Tri Dao, Beidi Chen, Nimit S Sohoni, Arjun Desai, Michael Poli, Jessica Grogan, Alexander Liu, Aniruddh Rao, Atri Rudra, and Christopher Ré. Monarch: Expressive structured matrices for efficient and accurate training. In International Conference on Machine Learning. PMLR, 2022.
[22] Beidi Chen, Tri Dao, Kaizhao Liang, Jiaming Yang, Zhao Song, Atri Rudra, and Christopher Ré. Pixelated butterfly: Simple and efficient sparse training for neural network models. 2021.
[23] Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, and Christopher Ré. Scatterbrain: Unifying sparse and low-rank attention. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[24] Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequences with struc- tured state spaces. arXiv preprini 1rXiv:2111.00396, 2021.
[25] Junxiong Wang, Jing Nathan Yan, Albert Gu, and Alexander M Rush. Pretraining without attention. arXiv preprint arXiv:22/2.1054:: 2022.
[26] Antonio Orvicto, Samuel L Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences. In Inter- national Conference on Machine Learning, pages 26670-26698, PMLR, 2023.
[27] Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752 2023.
[28] Soham De, Samuel L Smith, Anushan Fernando, Aleksandar Botev, George Murtau, Albert Gu, Ruba Haroun, Leonard Berrada, Yutian Chen, Srivatsan Srinivasan, et al. Grif- fin: Mixing gated linear recurrences with local attention for efficient language models. arXiv preprint arXiv:2402. 19427, 2024.
[29] David W Romero, Anna Kuzina, Erik Bekkers, Jakub Mikolaj Tomezak, and Mark Hoogen- doom. Ckconv: Continuous kernel convolution for sequential data. In International Confer- ence on Learning Representations, 2021.
[30] Yuhong Li, Tianle Cai, Yi Zhang, Deming Chen, and Debadeepta Dey. What makes convolu- tional models great on long sequence modeling? arXiv preprint 1r.iv:2100009298 2022.
[31] Michael Poli, Stefano Massaroli, Eric Nguyen, Daniel Y Fu, Tri Dao, Stephen Baccus, Yoshua Bengio, Stefano Ermon, and Christopher Ré. Hyena hierarchy: Towards larger convolutional language models. International Conference on Machine Learning. 2023.
[32] Sepp Hochreiter, Jürgen Schmidhuber, et al. Long short-term memory. Neural computation, 9 18):1735- 1997.
[33] Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher Ré. Combining recurrent, convolutional, and continuous-time models with linear state space layers. Advances in neural information processing systems, 34:572-585, 2021.
[34] Mahdi Karami, Dale Schuurmans, Jascha Sohl-Dickstein, Laurent Dinh, and Daniel Duck- worth. Invertible convolutional flow. Advances in Neural Information Processing Systems, 32, 2019.
[35] James W Cooley and John W Tukey. An algorithm for the machine calculation of complex fourier series. Mathematics of computation, 19(90):97-301. 1965.
[36] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learn- ing: Grids, groups, graphs, geodesics, and gauges. arXiv preprint arX1v:2104.13478, 2021.
[37] N Thomas, T Smidt, S Kearnes, I. Yang. L. Li, K Kohlhoff, and P Riley. Tensor field networks: Rotation-and cansslaaion-quivariann neural networks for 3d point clouds, arxiv 2018. arXiv preprint arXiv: /802 /9.
12

---

[38]
Alan V Oppenheim. Discrete-time signal processing. Pearson Education India, 1999.
[39]
Julius O Smith. Mathematics of the discrete Fourier transform (DFT): with audio applications. Julius Smith, 2008.
[40] Robert M Gray et al. Toeplitz and circulant matrices: A review. Foundations and Trends@ in Communications and Information Theory, 2(3):155-239) 2006.
[41] Marcin Moczulski, Misha Denil, Jeremy Appleyard, and Nando de Freitas. Acde: A structured efficient linear layer. arXiv preprint arXiv:1511.05945 2015.
[42] Yu Cheng, Felix X Yu, Rogerio S Feris, Sanjiv Kumar, Alok Choudhary, and Shi-Fu Chang. An exploration of parameter redundancy in deep networks with circulant projections. In Pro- ceedings of the IEEE International Conference on Computer Vision, pages 2857-2865, 2015.
[43] Daniel Y Fu, Hermann Kumbong, Eric Nguyen, and Christopher Ré. Flashfftccov: Efficient convolutions for long sequences with tensor cores. arXiv preprint arXiv:2311.05900 2023.
[44] Daniel Y Fu, Simran Arora, Jessica Grogan, Isys Johnson, Sabri Eyuboglu, Armin W Thomas, Benjamin Spector, Michael Poli, Atri Rudra, and Christopher Ré. Monarch mixer: A simple sub-quadratic gemm- based architecture. arXiv preprint arXiv:2310.122 2023.
[45] Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Ya- sunaga, Yian Zhang, Deepak Narayanan, Yuhuai Wu, Ananya Kumar, et al. Holistic evaluation of language models. arXiv preprint arXiv:2211.0911 2022.
[46] Shivam Garg, Dimitris Tsipras, Percy Liang, and Gregory Valiant. What can transformers learn in-context? case study of simple function classes. arXiv preprint (tt.::220000000666 2022.
[47] Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodee Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kamal Ndousse, Dario Amodei, Tom Brown, Jack Clark, Jared Kaplan, Sam McCandlish, and Chris Olah. In-context learning and induction heads. Transformer Cir- cuits Thread, 2022. http://ttassformerriruiisss httpb///22//ii-mmtteeeeeeeae -andiinnn--nd-iiee -nduddictiiion- heads/index.html.
[48] Jacob Devlin, Ming-Woi Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding, arXiv preprint arXiv:1810004805, 2018
[49] Yinhan Liu, Myle Out, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized BERT pretraining approach. arXiv preprint arXiv: /907. 1692, 2019.
[50] Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel S Weld, Luke Zettlemoyer, and Omer Levy. Spanbert: Improving pre- pre-training by representing and predicting spans. Transactions of the Association for Computational Linguistics, 8:64-77, 2020.
[51] Di Jin, Zhijing Jin, Joey Tianyi Zhou, and Peter Szolovits. Is BERT really robust? a strong baseline for natural language attack on text classification and entailment. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 8018-8025, 2020.
[52] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint 1910. 2019.
[53] Peter Izsak. Moshe Berchansky, and Omer Levy. How to train BERT with an academic budget. In Proceedings of the 202/ Conference on Empirical Methods Natural Language Process- ing, pages 10644-10652, 2021.
[54] David M Knigge, David W Romero, Albert Gu, Efstratios Gavves, Erik J Bekkers, Jakub M Tomezak, Mark Hoogendoorn, and Jan-Jakob Sonke. Modelling long range dependencies n d: From tpsk-specific to general purpose cnn. arXiv preprint arXiv:2301. 2001: 10540, 2023.
13

---

[55] Felix Wu, Angela Fan, Alexei Baevski, Yann N Dauphin, and Michael Auli. Pay less attention with lightweight and dynamic convolutions. arXiv preprint
2019.
[56) Yinpeng Chen, Xiyang Dai, Mengchen Liu, Dongdong Chen, Lu Yuan, and Zicheng Liu. Dynamic convolution: Attention over convolution kernels. In Proceedings of the IEEE/VVF conference computer vixion and pattern recognition, pages 11030-11039 2020.
[57] Zi-Hang Jiang, Weihao Yu, Daquan Zhou, Yumpeng Chen, Jiashi Feng. and Shuicheng Yan. Convbert: Improving bert with span-based dynamic convolution. Advances in Neural Infor- mation Processing Systems, 33:12837-12848, 2020.
[58) Zongyi Li, Nikola Kovachki, Kamyar Azizzadenesheli, Burigede Liu, Kaushik Bhattacharya, Andrew Stuart, and Anima Anandkumar. Fourier neural operator for parametric partial differ- ential equations. arXiv preprint (0Xi::0000008995. 2020.
[59] John Guibas, Morteza Mardani, Zongyi Li, Andrew Tao, Anima Anandkumar, and Bryan Catanzaro. Adaptive fourier neural operators: Efficient token mixers for transformers. arXiv preprint arXiv:2111.13558 2021.
[60] Simran Arora, Sabri Eyuboglu, Michael Zhang, Aman Timalsina, Silas Alberti, Dylan Zinsley, James Zou, Atri Rudra, and Christopher Ré. Simple linear attention language models balance the -hrouhuht tradeoff. arXiv preprint arXiv:2402.18666 2024.
[61] Nan Ding, Tomer Levinboim, Jialin Wu, Sebastian Goodman, and Radu Soricut. Causallm is not optimal for in-context learning. arXiv preprint arXiv:2308.069/2 2023.
[62] Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction. arXiv preprint arXiv:2403.06963, 2024.
[63] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 141.,690, 2014.
[64] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bow- man. Glue: A multi-task benchmark and analysis platform for natural language understanding. a7X1v.180.007461, 2018.
[65] Andreas Steiner, Alexander Kolesnikov, Xiaohua Zhai, Ross Wightman, Jakob Uszkoreit, and Lucas Beyer. How train your ViT? data, augmentation, and regularization in vision trans- formers. arXiv preprini arXiv:2 106. 10270, 2021.
[66] Lucas Beyer, Xiaohua Zhai, and Alexander Kolesnikov. Better plain VIT baselines for imagenet-lk. lk. arXiv preprint arXiv:2205.015880 2022.
[67] Li Yuan, Yumpeng Chen. Tao Wang. Weihao Yu, Yujun Shi, Zi- Zi-Hang Jiang, Francis EH Tay, Jiashi Feng, and Shuicheng Yan. Tokens-to-token VIT: Training vision transformers from scratch on imagenet. In Proceedings of the IEEF/CVF international conference on computer vision, pages 558-567, 2021.
(68] Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. FlashAttention: Fast and memory-efficient exact attention with IO-awareness. In Advances in Neural Information Processing Systems, 2022.
Broader Impacts
The introduction of Orchid, with its innovative data-dependent convolution mechanism, can poten- tially lead to impacts across various sectors of society.
Accessibility and Democratization of AI: By reducing the computational and memory requirements traditionally associated with deep learning models, Orchid makes advanced AI technologies more accessible to broader range of researchers, startups, and institutions.
14

---

Environmental Sustainability: The efficiency of Orchid, particularly in terms of compu- tational and energy demands, aligns with the urgent need for environmentally sustainable Al practices. Lower energy consumption contributes to reducing the carbon footprint of training and deploying large-scale models, aligning with global sustainability goals.
Advancements in Healthcare: In the healthcare sector, Orchid's ability to efficiently pro- cess long sequences of data could revolutionize early diagnosis and personalized medicine. For instance, it could enable more accurate analysis of genomic sequences or continuous health monitoring data.
15

---

A
Notation definition
Notations
Brief definition and interpretation
2. y. W
a R" and y R²' are input and ouiput sequence of a layer, while matrices are denoted by bold uppercase letters, such layer weight matris W.
h a
lincar convolution: yif (/a + a] Dian hip d]a[(]
circolar convolution: y 1.] (A [) Et hit mod M]r[1]]
ks q
cross-corrclation: As]1| (k+ g)({} A >> k g mod
h a
element-wise multiplication (Hadamard product): w[t] (h o m) Afd aft]
shiftm((x)
(ar))( m]
F0.F-
The forward and inverse discrete Fourier transforms while T represents the DFT matrix.
F(m)) Tn
à A zero-padded signal the defined padgg [0z;
(x))
padding the vector E R with zeros to the target size N, &ee. pad,, (at) [0w-z)] zi where [0x z|: zero voctor size (N L)).
he(ar)
conditioning network (data-dependent convolution kerelly; Au(mz) NNa that neural network parameterized by 8.
Convid
depthwise convolation with
length (typically 3-5) applied to each
feature dimension
FCO
dense fully connected layer PC(rr) =W +
Multi-Layer Perceptron which composed of dense fully connected layers
PosBnb()
positional emheading of time step
M(t)
positional encoding part of the convolution kemel: h(t) FFF (PoeEmb(())))
Remark A.1 (Orchid Combines Global and Local Mixing Operations in Spatial and Spectral Domains:). The core of Orchid is long, data-dependent convolution with an adaptive kernel span- ning the entire input sequence. This means that the convolution operation performed by Orchid mixes (convolves) the entire sequence globally using the proposed adaptive input dependent ker- nels. On the other hand, the conditioning networks responsible for generating this adaptive kernel operate locally in both the spectral and spatial domains.
Comparing self-attention to Orchid reveals further insights. The pair of mappings k(x) and q(x) in the conditioning network of Orchid (equation 3. are analogous to the key k(z) and query ((x) in the attention mechanism. In both models, these components are modeled using local neural networks: attention utilizes pointwise linear projections, while Orchid employs local Cone operations in both the spatial and spectral domains. The attention mechanisms calculate the input-dependent at- tention score matrix A(x) and subsequently compute the output as y = A(z)e. In contrast, Orchid conditioning network performs a cooosscorrelation-- global operation- Seetwennnbbetween k(x) and 4(x)) to derive the convolution kernel h(x)), followed by global convolution y = h((x) v. Therefore, while the inner blocks (the input-dependent networks that compute the convolution kernel in Orchid) oper- ate locally on the inputs, the outer blocks (such as the matrix product in attention, cross-coss cross-correlation convolution in Orchid) perform global sequence mixing. This approach ensures fixed (or sub- linear) parameter scaling with respect to sequence length, preventing the model size from growing excessively with sequence length.
Remark A.2 (Model Name:). The name "Orchid" for our model is more than just label; it carries a symbolic meaning for our model, reflecting its elegance, resilience, and adaptability. Orchids are known to thrive in diverse environments and exhibit subtle color variations under specific environ- mental conditions, including light intensity, seasonal changes, and dyeing. The essence of adaptation and efficient resource utilization resonates profoundly with our model's design. Moreover, the pro- posed model's computational efficiency aligns with more environmentally sustainable Al practices by minimizing energy consumption and carbon footprint during training and deployment.
16

---

B Proof
Proof for Preserving Shift Equivariance: Given a circular shift invariant filter kernel, where
ha + m mod L]) = ha (x]()).
For circularly shifted input, the circular convolution can be expressed as:
(ho(shiftm. (x)) @ shiftm (2)) (=ssifft..=)(()) shift.. (w) mod L]
he + ml) shiftm + m - mod L]
Σ ho(a)(() shiftm (x) m mod L. t=
y + m mod L]
shiftm
Therefore, if the filter kernel is shift-invariant, the conditional convolution will also be shift- equivariant.
C Experimental Details
C.1 Synthetic In-context Learning
We used associative recall task to evaluate in-context learning of the proposed model. Given string of key-value tuples from random dictionary, this task involves generating value from key For instance, given the input ([a, 1, e, f.fl. b), the model is expected to return e, the value associated with the key b. This task assesses whether model effectively retrieve the correct value from a key in a prompt, essentially applying a data-controlled shift. While attention mechanisms offer this capability by computing pair-wist attention scores and then weighting the entire sequence accordingly (4), they face computational difficulties for very large sequence.
The model is composed of 2 Orchid block while each Orchid is composed of chain of order 1.5. including glement-wiss. multiplications and one data-dependent convolution. The hidden size of all models in this experiments which was composed of a ID depthwise convolution (Convid) in the time domain and Convid in the frequency domain that were applied separately to each feature dimension, both having kernel of length 3. Only for vocabulary size of 40 with short sequence lengths of 128 we increased the depth to layers of Convid in the spatial domain and in the frequency domain.
set to 64. The conditioning network, defined in ② was used
For training, we used Adam optimizer learning rate of 5e-4 with linear warmup schedule in 1000 steps. A weight decay of () was used as a regularizer. The Orchid models were trained Orchid on single P100 GPU for small medium sequence length and on a single V100 GPU for long sequences.
6S with its standard settings (B) = .9, B2 .999), and
C.2 Model Architecture Ablation
To better understand the impact of different model components, we conducted several ablation stud- ies on in-context learning task in section 4.1 First, we evaluated different depthwise linear convo- lution architectures in the conditioning network, as outlined in Equation (2). This ablation study compared: I) Spatial then Spectral: applying Conv1D in the spatial domain followed by Conv1D in the frequency domain (as proposed in Equation (2)). II) Spatial Only: applying two ConviD 1D layers in spatial domain only, and III) Spectral Only: applying two Conv1D layers in the spectral domain only. The results, presented in Figure C. demonstrate that the proposed method of operating in both spatial and frequency domains (Equation offers the best performance. This approach effectively mixes information from neighboring tokens in both domains, capturing richer representations.
17

---

Teat Accurscy
02
Trainer 3100
50x
Figure C.I: Comparison of Local Conv1D Choices: Evaluation of different local convolution options used the conditioning network. Conditioning networks type (Equation [ (1 layer Conv1D in time 1 layer in frequency), layer Conv1D in time, 2 layer Conv1D in frequency, and 3 layer Conv1D in time 3 layer in Trequency.
Second, we compared the two conditioning networks for data-dependent convolution defined in Equations and 3 We also evaluated various nonlinearity o() functions used in the Type II (cross- correlation) conditioning network:
and
hig (a) Convid (Convid((x)) @ (F (Convid(z=)))
The nonlinearities includes {Tanh O) Sigmoid(), Softsign (), Softshrink(), Identity() 0) each applied only to the magnitude of its argument. The results in Figure CC. indicates that remov- ing this nonlinearity provides the best performance, slightly exceeding that of Softshrink() and Tanh (). Notably, among the nonlinearities those that cross zero perform better. Moreover, we ob- served that Type II conditioning networks (cross-correlation) with Identity and Softshrink( exhibit faster convergence compared to Type
Test Accuracy
Orcn DCT totherema Type 8.8 praernTem
CDTT lnthrren--llee 8. pro sobogg0
-rchi fos Pops kpp Cords
inhre
0.6
0.4
0.2
Trainer Step
10k
20k
30k
40k
50k
60k
70k
Figure C.2: Comparison of different o)) on conditioning network of Type Il (cross-correlation in equation
Finally, we evaluated two different Fourier transforms: Discrete Fourier Transform (DFT) and Dis- crete Cosine Transform (DCT). We considered both orthogonal and orthonormal versions of each transform. Orthonormal transforms utilize an orthogonal and normalized basis, resulting in a unitary transform matrix T. The results, presented in Figure C.3 show that Type I conditioning networks (Equation (2) exhibit faster convergence. Moreover, the DCT surpasses the DFT in terms of learning speed, likely because DCT corresponds to even-symmetrie padding, which smooths the signal at the boundaries compared to the circular padding the DFT. Furthermore, the DCT produces real- valued transforms. Notably, using orthonormal transforms accelerates the learning process. Conse- quently, we opted for the orthonormal DCT with Type conditioning networks for data-dependent convolution in all the experiments.
18

---

Test Accuracy
Orchid BCT-ortonommal
-rchid DFT.ortionnamal
-Orchid DCTI Type!
0.8
-Occhd DFT DFT-Type!
0.6
0.2
Trainer Step
120k
Figure C.3: Test accuracy of in-context learning the associative recall task with vocahulary size of 20 sequence length of 128, comparing different model components. Type refers conditioning networks of type I (based on ahsolute value in Equation 2). Orthonormal indicates transforms that utilize orthogonal and normalized bases.
C.3 Language Modeling
In our experiments, we replaced the attention layers in the standard BERT framework in 48 with Orchid layers. For each Transformer block in the BERT-style model, we replaced the attention layers with Orchid layers for sequence mixing. Each Orchid layer was composed of a chain order 1.5, including 2 element-wise multiplications and one data-dependent convolution. The conditioning network, defined in (2), was used which was composed of a short Convid time domain and Convid in the frequency domain that were applied separately each feature dimension, both having kernel of length 3. For dimension mixing, we also substituted the two dense matrices the MLP layers with block-diagonal matrices of order 1 with b 4 blocks 21 and also add residual long convolution to each Orchid layer, as 44
Our BERT-style model, called Brchid-BERT-BER of 768, the same dimension and depth as BERT-base resulting Orchid-BERT-bar BERT-base having 77M parameters, compared to BERT-base's 10M parameters. We also pre-trained Orchid-BERT-lan of 254M parameters with hidden dimensions of 1536 and 12 layers.
was composed of 12 layers with a hidden size
For pre-training, we used decoupled Adam optimizer with 31 of 8e-4 with linear warmup schedule within first 6% of the steps and then decay with linear rate. A weight decay of le-5 is used as regularizer. Orchid models were pre-trained using masked language modeling with 30% masking over the C4 dataset [52] with sequence length of 128 and the bert-base- cnsse-u tokenizer. Models were pre-trained on node of 4xA 100 GPUs for 70k steps with batch size of 4096.
3, = .9,, and learning rate
Finetuning GLUE Benchmark: To evaluate the performance of Orchid-BERT models, finetuned the pre-trained models on GLUE fine-tuning tasks, comparing them against the base- line models: BERT-base and BERT-large, and the recent long convolution- models: M2- BERT-base and M2-BERT-large [44]. The fine-tuning process was executed accordance with the methodology described by Izsak et al. [53]
For all tasks, the sequence length was 128. For some of the tasks, we applied average pooling on the embeddings of all the non-padding tokens and use it as the model output. We followed (53) in fine- tuning small dataset tasks: RTE, MRPC, and STS-B are initialized from the fine-tuned checkpoint of MNLI dataset. Models were fine-tuned
node of 4xA100 GPUs.
In contrast 144, which performed a hyperparameter search for learning rate, weight decay, and number of epochs, we used the reported hyper- parameters in [44] and didn't 't perform a thorough search for them. As noted in [53), hyperparameter search can result in substantial improvements in the performance. In particular for CoLAA task, whose results are bellow M2-BERT, we anticipate that fine uning the parameter will improve its performance. The detailed hyperparameters for each task is reported in Table C.2
19

---

Table C.I: A summary of the Fine-tuning results on GLUE benchmark 64
Following the the methodology
outlined in 53 we use the standard evaluation metries: Spearman's 's correlation for STS-B, B, Matthew's 's corre- lation for CoLA, Fl scores for QQP and MRPC, and accuracy for the other tasks. For MNLI, the average of
multiclass accuracy (m) both multiclass accuracy of mismatched set (mm) is used.
Model
MNLI (m mm)
RTE
QNLI
QQP
SST2
STS-B
CoLA
MRPC
Average
M2-BERT-hbse (80M)
78.4/ / 77.66
68.5
84.6
86.7
92.0
86,3
53.0
89.8
79,9
Orchid-BERT--use (77M)
79.53 / 80.52
70.4
86.16
87.2
92.05
86.63
51.76
90.53
80.6
M2-BBRTT-large (260M)
81.7/81
72.8
84.7
87.8
93.3
88.0
59.2
90.0
82.2
Orchid-BEnE Beld--BBRTlagge (254M)
81.2/ / 82.74
76.32
87.02
88.18
92.8
88.29
56.97
89.24
82.65
Hyperparameters for Orchid-bert-ban bert-base (77M) and Sechid-BERT-large (254M) on Various GLUE Tasks, D-AdamW V stands for Decoupled AdamW optimization algorithm. For QNLI task in Orchid-bert-ee (77M) we applied everage pooling.
Table C.2:
Hyperparameter
MNLI
RTE
QNLI
QQP
SST2
STSB
CoLA
MRPC
Orchid-bert-base (77M)
Optimizer D-AdamW
A 5e-5
AdamW 5e-5
AdamW
D-AdamW 36-5
AdumW 7c-5
D-AdamW 50-5 5e-6
AdamW Se-5
Learning Rate
5c-5
3e-5
Waight Decay
5e-6
0.01
0.01
0.01 10
Epochs
3
6
10
10
10
10
Orchid-hert-large (254M)
Optinizer D-AdamW
D-Adam le.5
D-AdamW
D-Adam 3e-5
D-AdamW 3e-5
D-AdamW
AdamW 5e-5
D-Adam
Learning Rate
5e-5
5e-5
7e-5
Ke-5
Weight Decay
Se-6
le-6
le-5
3--6
3--6
3--6
Se-6
8e-6
Epochs
3
10
10
10
C.4 Image Classification
We extended the application of Orchid the Vision Transformer (ViT) architecture, introduced by Dosovitskiy et al. [2]. by replacing its attention mechanism with Orchid similar to language modeling task. The sinusoidal positional embeddings and global average-pooling were employed for the class token, following (65 66). We compared the performance of our model against recent
long convolution-ben based models, specifically Hyena- Hyena-ViT-b [31 and M2-ViT-b 44. We evaluated the models on two widely used image classification datasets: CIFAR-10 10 and In..
Each Orchid layer consists of chain of order 1.5, involving 2 element- wise multiplications and one data-dependent convolution. The conditioning network (defined in Eq. 2 employs a combination of Convid layers in both the time and frequency domains, applied separately to each feature dimension with a kernel length of 3 and 5 for CIFAR-10 and ImageNet- 1 K, respectively.
CIFAR-10: For CIFAR- 10, images were transformed into sequences of 4 x 4 pixel patches and processed using a ViT architecture composed of 6 Transformer layers with hidden sizes of either 128 and 220 for Orchid-s and Orchid-m, respectively. For training, we used Adam optimizer with its standard setting (3) = .9, B2 = .999), and learning rate of 3e-4 with linear warmup schedule within first 500 steps. For the experiments (Ie-3, 5e-3, le-2). A weight decay of 0.05 was used as regularizer. Orchid was trained on a single P100 GPU for 500 epochs with batch size of 512.
Orchid-s (4 x 4), tuned base learning rate over
ImageNet-IK:
We segmented images into patches of 16 x 16 pixels, and we trained a ViT-base architecture featuring 12 Transformer layers and hidden size of 768. We incorporated residual long convolution within each Orchid layer and substituted the dense matrices in the MIP layers responsible for feature mixing with block-diagonal matrices of order with blocks. reducing their computational complexity and the total model's size.
For training, we used Adam optimizer with its standard setting (31 .9, 32 = .999), and base learning rate of 1e-3 with linear warmup schedule within first 10 epochs and then decay with Co- sine schedule. For data augmentation, we adopted the T2T-VIT pipeline (67), including Random erasing with rate=0.25, CutMix with d=1.0, Mixup with a=0.8, AugMix, and RandAugment with (magnitude=9, magnitude-std-0055 layers=2]. We trained Orchid on 4x 100 GPUs for 300 epochs and batch size of 1024.
Table C.3 summarizes architecture and training settings.
20

---

Table C.3: Architecture and training settings for Orchid models.
ImageNet- Ik
CIFAR 10
Number of Orchid blocks
Hidden dimension
768
128, 220
Short Convid kernel size PosEmb dimension Patch size
5
33
16
4
Batch size
1024
512
Training epochs
300
500
Weight decay
0.05
0.05
Learning rate schedule
Cosine decay with linear warmup
Constant with linear warmup
Base learning rate
le-3
(1e-3, 5e-3, le-2)
Warmup Label smoothing
10 epochs
500 steps 0.1
0.1
Accuracy the Speech Commands dataset with 10 classes, S4-M2 refers to the S4 model 24 where dense matrices in the MLP layers replaced with block-diagonal matrices. Baseline results are sourced from [4), and x indicates that the Transformer model could not fit in GPU memory.
Table C.4:
Transformer
Performer
CKConv
WaveGan-D
S4-M2
Orchid
x
30.8
71.7
96.3
97.5
97.9
97.7
C.5 Speech Classification
To evaluate the ability learn long-range dependencies in real-world time-series data, we con- ducted experiments on the speech classification task using the SC10 subset of the Speech Commands dataset, which contains 10 classes. Following [29], we use the raw speech dataset with 1-second du- ration sampled at 16000 Hz for this task. The performance results shown in Table Table|C.4] highlight that Orchid performs on par with the state-of-the-art model on this long sequence modeling task.
C.6 Runtime Benchmark
To assess the computational efficiency of Orchid, we benchmarked its runtime against both tradi- tional attention layers and the optimized FlashAttention mechanism [6.].The evaluation was con- ducted on an NVIDIA A100-40GB GPU with models featuring hidden dimension of 768 and batch size of The empirical runtime comparisons in Figure C.4 highlights Orchid's high scal- ability, especially for longer sequences. Here, FlashAttention utilizes float16 precision, while Attention and Orchid use float32. It's worth noting that Orchid's convolution operators utilize standard FFT implementation in PyTorch, and further speed improvements are anticipated with the integration fused CUDA kernels FlashFFT 43
21

---

Comparison (Forward)
FlashArtention
200
Attention
Rontime (ms)
Orchid
100
217
Sequence Length (L)
Comparison (Rack-propagattoon)
600
MHA Orchid
400
Runtime
200
Sequence Length (L)
Figure C.4: Forward backward runtime comparison different attention mechanisms Attentnn Atlention, and Orchid) with varying sequence lengths.
22

---

D Implementation
1 import torch
2 import torch. nn as un from torch_dct import dct, idct
from einops import rearrange
6 class DiscreteTransfom (nn. Module):
def --init_... (self, mode- "dct", norm-" ortho", dim-1):
super () -- iniiinit_ ()
self.din dim dim; self mode mode; self..
def forvard x):
if self mode == "dct":
det dim=self dim, n shape [self dim])
return rearrange det (zearrange "b d 1"), norm=self. b
15
elif melf.mode "fft": return torch... fft. (xf dim-self.dim)
def inverse x):
19
self "dct":
return idct(x, dim=self. dim, n (aelf.imm))))
elif self. -- "fit":
return forch.fft.rn irftiffftx dim=self dim)
class OrchidOperator (an Module):
def ...itt_.. (self, d, L, d_filter=64, 1_convid=3, dxt_mode="fft", vo_out_ppooj=True
self.d_model d self len L
setup projections self. in in_line nn. Linerr (d, 3+d)
if to_ to_out_prooj aalf.out_lineas
mn Linear (d, d)
setup short conv filter width d * www.ts mn. Convid(vidth width,
sernel_size-1_corv/l groups-width, paddng=1_convid-1]
setup static conv The implementation of static conv in Hyena (inspired by CKConv) was used. A basic implementation is:
(emb_ dim, 1), nn Linear (emb_dim, d.filter), Sin(), mn Linear (d_filter, dfiitter, ExponentiallMouulatii ()) self static. = (dConv order=d_filter seq_len=L)
nn nn. Sequential (ogpraaallPssttttnnnaabaaaaaaaa
Setup conditioning network. See shift invariant model: self conditioning_an nn ( mn convidd,, d, l_convid, d, padding=1_comvtddl)) DiscreteTransform an.
52
(anetTTTrantommooooettttttooooo (node=dxtxx_ood dim=1),
cn.conii (d, d, l_convid, d, coding--1.con1dd11),
self transform = DiscreteTransforas (mode=dxt_mode dim=-1)
def forvard x, **warggs):
(b, 1,
61
x self innfear (x)
-. torch. split self m_odee dim=-1)
h_adapt_f self conv (onv_kermee_nnvv) Input dependeet Kernel
23

---

h_0 = stattitctcccoov.fiii wflfteeerreer (self. seq_len)
h_0 rearrange (h_0, "c d -> d 1")
short convid() filter
rearrange "b 1 d >> b d 1")
-self. short_ (x) (x) :self seq_len]
s1, =2, v= s.xpppitseeef d_model, dim=1)
v * s1
y self. adaptive_conv (y, b_0-h_0, a
y y * s2
rearrange "b 1 a1a)
if self. tolf.to.oute out.poooo.or
y self out_ (y)
return y
def Seaative_conv(eeee x, h_0, h_adapt_f): x is (b, a, 1) x_f self (x)
h_0_f (ransttrooooom
y torch. fich (xff (h_0_f h_adapt_f))
return y(..., :self seqlen]
Listing 1: A basic implementation of the Orchid layer.
24

---

NeurIPS Paper Checklist
The checklist designed to encourage best practices for responsible machine learning research, ad- dressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes]. [No]. or [NA]-
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evalu- ation. While "[Yes] is generally preferable to "[No] it is perfectly acceptable to answer "[No] provided a proper justification is given (e.g., "error bars are not reported because would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] " not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, so please just use your best judgment and write a justification to elaborate. All supporting evidence can appear either the main paper the supplemental material, provided in appendix. If you answer [Yes]] to question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]-
Justification:
The main claims made in the abstract and introduction are supported by the evidence pre- sented in the paper.
Effectiveness: The experiments on in-context learning (Section 4.1), language modeling (Section 4.2), image classification (Section 4.3), and speech command classification (Ap- pendix C.5) demonstrate the effectiveness of Orchid.
Long sequence modeling capability: The in-context learning experiments evaluate the model's ability handle long sequences, and the speech command classification task fur- ther confirms this capability on real-world data.
Scalability: The analysis in the main text and the empirical runtime comparison in Ap- pendix C.6 provide evidence for Orchid's quasi-linear scalability, supporting the claim of improved scalability compared to attention-based models.
Guidelines:
25

---

The answer NA means that the abstract and introduction do not include the claims
made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes].
The paper addresses the limitations of the proposed Orchid model in several sections. Section [6 discusses the general limitations of the model. Section details the spe- eific bottlenecks of FFT algorithms, such suboptimal hardware utilization and slow I/O between layers, and discusses potential solutions. Sections 3.3 and 2 discussed the com- putational efficiency the model. Empirical runtime comparisons with standard attention mechanisms, presented in Appendix C.5
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "L.imitttoons" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-texx system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes].
Justification: The paper clearly states the assumptions and provides a proof for the shift invariance conditional convolution in Appendix B relevant theorems and lemmas.
We also provided the references to
26

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes].
The paper provides a comprehensive description of the Orchid model ar- chitecture, including the conditional global convolution layer and the two shift-invariant conditioning networks, in the main text and Appendix [ Additionally, basic Python implementation code for the model is provided in Appendix D further facilitating repro- ducibility, Experimental details sufficient to reproduce the main results are also included in the experimental section and Appendix
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on contribution, reproducibility can accomplished various ways. For example, if the contribution is novel architecture, deseribing the architecture fully might suffice, or the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
also be provided via
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibiliiyy In the case of closed-source models, it may be that access to the model is limited in
27

---

some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes].
Justification: We provide a basic Python implementation of the Orchid model in Appendix D While we did not generate new datasets for this study, we utilized publicly available datasets that have been used in relevant baseline studies. We have cited the original sources of these datasets and provided detailed description of the preprocessing steps applied in the supplemental material. This should allow others to faithfully reproduce our main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please the NeurIPS code and data submission guidelines (https://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips. poc/public/aae wwwpce/ggudge/eege Cwwe//ooeeeeeeeeeeee sesisssssooollo onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes].
Justification: the paper provides comprehensive description of the experimental setup and details in Appendix C
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question:
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
28

---

Answer: [NA]
Justification: As in most baseline studies, the paper does not compute error bars due to the computational constraints associated with large language models and image datasets. However, for GLUE tasks, the performance is reported as an average across tasks, following the methodology used in the baseline studies.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors verified.
For asymmetric distributions, the authors should careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes].
Justification:
We provided the compute resources used for the experiments in the Appendix
C
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary failed experiments that didn't it make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpaa////arrrpp.cccpppphahhtata ieee
Answer: [Yes].
Justification:
We respected NeurlPS Code of Ethies.
Guidelines:
29

---

The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes].
Justification:
Broader impacts is included after the reference section.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses
(e.g., disinformation, generating fake profiles, surveillance), fairness considerations
(e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI...
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA].
Justification:
This work doesn't involve data models that have a high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by quiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
30

---

12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA].
We used open source codes and packages together with publicly available datasets.
Justification:
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, wwppssaipeaaiaaee thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of a dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information not available online, the authors are encouraged to reach out to the asset's ' creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA].
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmoell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer:[NA].
Justification:
Our work doesn't involve research with human subjects and crowdsourcing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
31

---

Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, cura- Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
tion, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Answer:[NA].
Justification:
Our work doesn't 't include research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as institution conducting the review.
32


Reviews:
[{"review_id": "2nOlwpEBwW", "reviewer": "Reviewer_pFWN", "summary": "Authors introduce a method for addressing the quadratic computational complexity of the attention mechanism while retaining expressivity and model performance from transformer models. Whereas previous approaches have achieved sub-quadratic computational efficiency - e.g. hyena, ssms and CKConv - authors argue (and show in their experiments) that these approaches limit model expressivity and performance - specifically in in-context learning settings. To this end, authors propose a novel long-range convolutional layer that is data-dependent, i.e. conditioned on the input. Orchid retains shift-equivariance properties of conventional convolution-based architectures, while being more expressive. Authors show superior performance over previous approaches in different domains (text and image data).", "questions": "- Regarding the synthetic in-context learning task, I might be misunderstanding something, but why are shorter sequences more challenging in this task (i.e. Hyena/ CKConv/H3 achieve lower accuracy on shorter sequences)? Isn't it generally more challenging to capture longer-range dependencies?\n- Why do you choose not to compare against CKConv [1] or a later improvement CCNN [2] in the image classification task (these models ? These methods achieve substantially better results on CIFAR, making me question the validity of your claims regarding the advantage of your model in a broad range of application domains.\n\n[1] Romero, D. W., Kuzina, A., Bekkers, E. J., Tomczak, J. M., & Hoogendoorn, M. (2021). Ckconv: Continuous kernel convolution for sequential data. arXiv preprint arXiv:2102.02611.\n[2] Knigge, D. M., Romero, D. W., Gu, A., Gavves, E., Bekkers, E. J., Tomczak, J. M., ... & Sonke, J. J. (2023). Modelling Long Range Dependencies in $ N $ D: From Task-Specific to a General Purpose CNN. arXiv preprint arXiv:2301.10540.", "limitations": "Authors sufficiently discussion limitations of their approach.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Authors introduce an innovative method for increasing the expressivity of subquadratic methods for long-range dependencies. \n- The paper is well-written, authors explain and motivate their modelling choices well, and provide helpful figures.\n- The approach of conditioning convolutional kernels based on input data is interesting in its own right and might warrant exploration in architectures not specifically tailored for modelling long-range dependencies.", "weaknesses": "- Limited set of experiments and comparisons against baselines. Although authors show results also on image data, they do not compare against 2D-convolutional long-range approaches which flimits interpretability of the results.\n- Authors do not thoroughly explore their shift-invariance constraints, which might not be appropriate in all settings, i.e. I can imagine that for textual data absolute positioning in a sentence does impact semantic meaning. On the other hand, authors provide good motivation for their choice of shift-invariance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and valuable feedback. We appreciate your recognition of the contributions and the strengths of our paper. In the following, the points you raised in your review are addressed.\n\n- *W1: Compare against 2D-convolutional long-range approaches:*  \nThe Orchid block, with its input-dependent long convolution, local depthwise linear convolution (Conv1d), and element-wise multiplications, is inherently extendable to multi-dimensional data.\nHowever, our primary focus in this work was on designing an efficient and scalable architecture specifically for sequence modeling. Expanding our comparisons to include 2D-convolutional long-range approaches, while valuable, was beyond the scope of our current study and is an interesting future work.  \nRegarding your point on the limited set of experiments against baselines, Appendix C5 also explores the ability of Orchid to learn long-range dependencies in speech classification tasks with long sequences. In these experiments, we compared Orchid against CKConv, Performer, and SSM-based models.\n\n\n- *W2: Absolute positioning in a sentence might impact semantic meaning:*  \nOur approach to shift invariance focuses on preserving the relational positions of tokens. While changing the order of the tokens/words and their absolute positioning might impact the semantic meaning, we expect that if an entire sentence is shifted and pad tokens are appended before or after it,  the sequence retains its semantic meaning. Indeed the relational positions of the tokens remain consistent in such cases.  \nFurthermore, the positional embeddings added to the token embeddings, at the beginning of language models, encode the absolute positions of the tokens, enabling the model to generate semantic differences when the order is changed. Moreover, ​​to achieve a location-dependent filtering scheme, we complement the data-dependent convolution with element-wise multiplications which allows the model to emphasize specific tokens in a sequence. \n\n- *Q1: Why are shorter sequences more challenging in the in-context learning task?*  \nShorter sequences pose a unique challenge in in-context learning tasks because specific (key, value) pairs appear less frequently within the string. This reduced frequency means the model has fewer opportunities to learn and generalize these associations. Additionally, when the vocabulary size also increases, the task becomes even more challenging for the model. The combination of infrequent pair repetitions and a larger vocabulary require a more expressive model architecture to effectively capture and utilize these (key, value) pairs within shorter sequences.\n\n- *Q2: Compare against CKConv variants:*   \nFixed long convolution kernel term (bias term) in Orchid and also convolution kernel in Hyena and M2 model are built upon long convolution kernel in CKConv, so by comparing against Hyena and M2 we explore the impact of the proposed input-dependent convolution that was introduced by Orchid model. \nMoreover,  in speech classification tasks with raw speech, Orchid is compared against CKConv.", "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": "", "extra_scores": {}}, {"review_id": "qL4uyX7uQE", "reviewer": "Reviewer_D4Wg", "summary": "This paper presents Orchid, a novel method that conditions long convolutional layers based on the input, to obtain global context and in-context learning abilities. This is achieved through the use of a conditioning network that acts both on the spatial and frequency domain to mix close spatial and spectral tokens, respectively. The resulting model surpasses other subquadratic models like Hyena and M2. It’s empirical results are compelling demonstrating the abilities of the proposed model over BERT and ViT-like models.", "questions": "- Line 27. Please add references.\n\n- In the appendix C.2, the authors state that Type-I conditioning combined with DTC seems to work best. Is this truly the case? If so, then I do not understand why other components are introduced that are not used at the end. Note that Type I is much simpler than Type II, both conceptually, in terms of implementation and speed. If this is the case, then that space can also be rather used for things that are used in the experimental section.\n\n- The authors also introduce data dependent convolution as an alternative to Cross-attention. But then, never use it. Again, this space can be better used to outline the components that are used in the experiments, or to extend the experimental section of the method.", "limitations": "The authors clearly state the limitations of the proposed method.\n\n### Conclusion\n\nWhilst I very much like the idea proposed here, and acknowledge its novelty and potential impact, I am not sure that in its current for this paper would be as impactful as I believe it could be. Therefore, I am hesitant to support acceptance. Note that I strongly believe that this paper could be very impactful. However, I believe that multiple adjustments must be made. With that being said, I am happy to increase my score should my concerns and comments be addressed.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "- The idea for input-dependence of convolutional kernels presented in the paper is novel, sound and very appealing.\n- The empirical evidence shows compelling evidence of the proposed model abilities.", "weaknesses": "- In my understanding, I am afraid that certain parts of the proposed model oversell what the model is capable of. Specifically, in Line 125, the authors argue that \"This allows each input token to attend to the entire sequence with personalized, adaptive weights derived from its specific representation\".  However, to the best of my understanding, Orchid only considers local information --both spatial and spectral-- for conditioning. See also Line 302-304 and 308. The authors should be clear and fair regarding the abilities of the proposed model.\n\n- i am afraid I do not truly understand the Orchid block. Note that Figure 2.1 has an MLP block at the beginning of the block, which is then completely ignored both in the text and in the reference implementation. I would strongly encourage the authors to clearly state how the Orchid block works in practice.\n\n- Although encouraging, I feel that the empirical section misses many important components that would improve the impact and adoption of Orchid.\n  - First, the associative recall tasks are only compared with other long conv models, some of which have been previously shown not to work in such tasks, e.g., H3, CKConv. For Orchid to be adopted in practice, I think that it would be very important to compare both to existing Transformer-like architectures as well as exiting input-dependent SSMs, e.g., Mamba.\n  - Related to the previous comment, Mamba has shown that existing long conv models do not perform well in the selective copying task. How does Orchid perform in this task?\n  - On the BERT experiments, the authors should include ablation studies to study the impact of using M2-MLP blocks as opposed to normal ones. It is not clear how much of a benefit (or decrease) results from this replacement, which is not inherent to Orchid.\n  - On the image classification experiments, the authors compare with methods that perform very poorly, e.g., 84% acc on CIFAR-10. I would encourage the authors to compare to more relevant existing methods. \n  - Related to the previous comment, one of the main advantages of long-conv models and Orchid is the fact that patches can become very small. If the accuracy results from the previous comment are limited by patchification, it would be very interesting to explore the performance differences when this module is removed. \n  - Related to the previous comment, the same experiment would be very valuable for ImageNet1k. Recent papers have shown that the smallest the patch the better the accuracy. Showing that Orchid scales well to ImageNet in this setting would be very appealing and would also potentially increase the impact of the paper.\n  - Still on the image processing setting, as far as I understand, it is very easy (not to say trivial) to expend Orchid to 2D data. Is there any reason as of why the authors did not use 2D orchid blocks for the image tasks?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive feedback on our paper. We appreciate your recognition of the novelty and soundness of our approach, as well as the compelling empirical evidence. In the following, we address the points you raised in your review.\n\n-  *Orchid is using local info for spectral and spatial:*  \nIn the proposed method, the long data-dependent convolution has an adaptive kernel that spans the entire length of the input sequence. This means that the convolution operation performed by Orchid indeed mixes the entire sequence globally using the proposed adaptive input dependent kernels, rather than being restricted to local windows. \nWhile the conditioning network’s input are local windows in both the spectral and spatial domains to determine the adaptive kernel, the convolution itself applies this kernel across the entire sequence. Thus, each input token is effectively mixed (convolved) with the entire sequence,\n\n-  *The role of MLPs at the beginning of the block:*  \nThe MLPs included at the beginning of the Orchid block serve as feature (dimension) mixing components that are commonly used in various sequence modeling architectures, such as Hyena, M2, and SSM. In practice, these MLPs perform a pointwise mixing of features, which is a standard technique employed both before and after sequence modeling operations in architectures like transformers.\nSince the main focus of our paper is on sequence modeling using the data-dependent global convolution mechanism the text focused on these parts in detail. However, we will clarify the role of these MLPs in the final version. \n-  *Impact of using M2-MLP blocks on the final results:*  \nIndeed the impact of using M2-MLP blocks can be analyzed by comparing Orchid and M2. In the experiments we compare Orchid with M2 of similar size, while both are using Block diagonal for MLP, the main difference between M2 and Orchid based architectures is that, in Orchid we deployed the proposed data-dependent long convolution while M2 is following Hyena in using a fixed long convolution. Therefore, the performance improvements observed in Orchid compared to M2 are attributed to the data-dependent sequence mixing mechanism \nUsing Block diagonal for MLP indeed will result in a sparse implementation of a dense MLP so it reduces the overall number of trainable parameters and reduces computational complexity\n\n**Questions:**  \n\n-  *Q1: reference for line 27* \nThank you for pointing this out.  We will add the references to support the statements such as [1]  \n\n\n-  *Q2: Why Type II is introduced in the text?*\nThe Type II (cross-correlation) approach generalizes the Type I (magnitude-based) approach and encompasses it as a special case. The introduction of Type II was intended to provide a more comprehensive view of the conditioning techniques available.\nMoreover, recent ablation studies, detailed in the rebuttal PDF, indicate that Type II combined with DCT performs better than Type I with DCT. \nHowever, since it is slightly more efficient in speed and parameter counts, Type I with DCT was selected for the in language, vision and audio experiments reported in our paper\n\n-  *Q3: Cross-attention functionality of Orchid:*   \nIn the text we emphasize the novel capabilities of the Orchid model.\nThe other long convolution based methods, such as Hyena and M2, and SSM-based methods such as Mamba, are not inherently applicable as an alternative to Cross-attention, so in this work we emphasize that the Orchid model is not only input-dependent but also its kernel can be conditioned on the an arbitrary input of any length so we call it data-dependent to infer more general than input-dependent modules. Implementing this ability of the proposed model could be a valuable direction for future work.\n\n\n[1] Nguyen, Eric, et al. \"Hyenadna: Long-range genomic sequence modeling at single nucleotide resolution.\" Advances in neural information processing systems 36 (2024).", "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": "", "extra_scores": {}}, {"review_id": "rvE4IzxNdD", "reviewer": "Reviewer_nmxo", "summary": "This paper introduces the Orchid block, a novel sequence modeling element that employs a convolutional operator with a sample-dependent generated kernel and an $O(n \\log n)$ computational complexity with $n$ being a sequence length. The kernel, matching the input sequence length, captures both long- and short-scale dependencies. As would be expected of a similar sequence processing operation, the authors design the kernel generator to be translationally-invariant. The proposed architecture is evaluated on language modeling tasks and image classification (ViT), with experimental results suggesting it outperforms established models like BERT and ViT, as well as recent architectures such as Hyena Hierarchy and Monarch Mixer.", "questions": "1. In Equation (3), it is not specified how the nonlinearity $\\sigma$ is applied to a _complex_ Fourier spectrum $\\mathcal{F}(\\dots)$. For the resulting product of $\\mathcal{F}^*(\\dots) \\odot \\sigma(\\mathcal{F}(\\dots))$ to be translation-invariant, it is important that $\\sigma$ preserves the phase of the complex number to which it is applied. It makes me conclude that the nonlinearity $\\sigma$ acts on the magnitude of the argument, but preserves the phase. Another naive alternative would be to apply $\\sigma$ to real and complex parts separately, but this would not preserve the phase and would thus break translational symmetry. Is my understanding correct? And if so, how is $\\sigma$ computed in current experiments? If this is correct, I also urge the authors to clarify this point in the publication.\n2. There are at least two [Fu et al., 2023] papers being referenced, which creates confusion.", "limitations": "The paper does discuss several limitations, of which perhaps the most important one is that it cannot be currently applied to causal models. Authors also highlight the fact that the proposed layer can serve as an alternative to the cross-attention layer. Furthermore, several seemingly arbitrary choices in the model architecture could also be re-evaluated in the future work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written and provides clear justification for the core elements of the proposed architecture, including the choice of the sample-dependent, translation-invariant convolution kernel generator.\n2. The proposed Orchid block is generally sound (see a question below). The experiments appear to be adequate to evaluate the proposed technique.\n3. Empirical results demonstrate that the proposed architecture offers a notable improvement over established Transformer baselines, as well as Hyena Hierarchy and Monarch Mixer models (other recent long convolution-based models). The resulting architecture thus presents a promising advancement.\n4. Inclusion of the synthetic in-context learning dataset highlighted an additional significant property of the proposed model: its ability to perform basic associative recall task even with very long sequences.", "weaknesses": "1. One weakness limiting a potential significance of this work is that the proposed model cannot be currently applied to causal models. But this can hopefully be addressed in the future work.\n2. While the proposed architecture is sub-quadratic and has the capability to efficiently process large inputs, it's crucial to evaluate its performance on real-world very long sequences (not just synthetic toy examples). Current approaches can scale Transformer-based models up to even millions of tokens and it could be quite crucial to demonstrate comparable performance for such long sequences as well.\n3. While the design of the translation-invariant generator is sufficiently principled, there are quite a few seemingly arbitrary choices (some nonlinearities, specific function dependencies and more) and a more careful ablation study could be required in the future.", "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": "", "extra_scores": {}}, {"review_id": "8n4700RpTN", "reviewer": "Reviewer_eXPv", "summary": "This paper introduces Orchid, a novel deep learning architecture that addresses the quadratic complexity of traditional attention mechanisms while still capturing long-range dependencies and enabling in-context learning. The key innovation is a data-dependent global convolution layer that dynamically adapts its kernel based on the input sequence using a dedicated conditioning neural network. Two simple conditioning networks are designed to maintain shift equivariance in the data-dependent convolution operation. The dynamic convolution kernel allows Orchid to achieve high expressivity with quasilinear scalability for long sequences. Experiments across language modeling and image classification tasks demonstrate that Orchid outperforms attention-based models like BERT and Vision Transformers with smaller model sizes. It also enables processing longer sequences beyond the limitations of dense attention layers.", "questions": "Please address the questions and concerns provided in the Weaknesses section", "limitations": "The authors have talked about various limitations of the paper.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper introduces Orchid, a novel deep learning architecture that addresses the quadratic complexity of traditional attention mechanisms while still capturing long-range dependencies and enabling in-context learning. The key innovation is a data-dependent global convolution layer that dynamically adapts its kernel based on the input sequence using a dedicated conditioning neural network. Two simple conditioning networks are designed to maintain shift equivariance in the data-dependent convolution operation. The dynamic convolution kernel allows Orchid to achieve high expressivity with quasilinear scalability for long sequences. Experiments across language modeling and image classification tasks demonstrate that Orchid outperforms attention-based models like BERT and Vision Transformers with smaller model sizes. It also enables processing longer sequences beyond the limitations of dense attention layers. The paper is well-written, with clear descriptions of the Orchid architecture and comprehensive empirical evaluation.", "weaknesses": "1. Citation issue: On page 3, there seems to be an issue with the citation at the end of the page. Could the authors please clarify and correct this?\n2. Computational complexity: Since the weights in the proposed method come from a neural network (data-driven), wouldn't this increase the computational complexity as the number of layers increases? In general, convolutional blocks do not have data-driven parameters. Could the authors provide more details on how the computational complexity scales with the number of layers?\n3. Conditioning networks: To improve the understanding of the paper, could the authors provide more details about the two conditioning networks introduced in the manuscript?\n4. Experiments: Which conditioning network is used in the experiments presented in the main paper? Clarifying this would help readers better understand the experimental setup and results.\n5. Block-diagonal matrices: The authors mention the use of block-diagonal matrices in the MLP layers for dimension mixing. However, the paper does not provide an ablation study to assess the impact of this design choice on the model's performance and efficiency. Could the authors include such an analysis to justify the use of block-diagonal matrices and provide insights into their role in the overall architecture?\n6. Interpretability and explainability: The paper does not provide a detailed analysis of the model's interpretability and explainability. Could the authors develop and discuss techniques to visualize and interpret the learned representations and decision-making process of Orchid? This would help improve the model's transparency and trustworthiness.\n\nGrammatical correction:\n\n- \"Moreover, its allows for handling very large sequence lengths that are beyond the limitations of the dense attention layers.\"", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces Orchid, a novel approach to enhancing the expressivity of subquadratic methods for long-range dependencies through a data-dependent global convolution mechanism. The reviewers generally agree that the paper offers a significant contribution to the field of sequence modeling, with potential applications across various domains such as text and image data (pFWN, nmxo, eXPv). The strengths of the paper lie in its clear justification of design choices, soundness of the proposed architecture, and empirical results that demonstrate improvements over established models like BERT, ViT, and recent architectures like Hyena Hierarchy and Monarch Mixer.

However, some concerns were raised by the reviewers that should be addressed. One notable issue is the “flag planting” concern highlighted by D4Wg, where the paper introduces elements such as Type II conditioning and cross-attention alternatives without fully integrating them into the main experimental validation. While the authors have provided additional experimental results and clarifications, it is important that the final manuscript clearly distinguishes between fully validated contributions and ideas that have not been extensively tested. Other concerns include the need for more thorough comparisons with baselines such as CKConv (pFWN) and further validation on practical datasets beyond synthetic data (nmxo).

Despite these concerns, I believe the novelty and potential impact of the proposed method outweigh the issues raised. I recommend accepting the paper, with a strong suggestion to the authors to revise the manuscript to clearly delineate between validated contributions and those that require further exploration. This will help ensure that the paper accurately reflects the state of its contributions and supports future research in the field.
Decision: Accept (poster)