Orchid: Flexible and Data-Dependent Convolution for Sequence Modeling

Authors: mahdi  karami
ali  ghodsi
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 09:11:07

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.

Main paper: 
 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-context tasks. This complexity has driven a shift towards innovative solutions to overcome this computational barrier, enabling analysis of long sequences in areas like genomics, DNA sequencing, and the creation of 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 learning 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 et al., 2020] Sparse Sinkhorn attention [Tay 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., 2020] which projects keys and values matrices to lowerdimensional 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 a combinations of such techniques to design an efficient transformer [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 et al., 2021,] .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 Poli et al., 2023] . A state space model characterizes a dynamical system's behavior in terms of its internal state using a 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. 1 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 et al. [2023] demonstrated that directly parameterizing the filter impulse response of the long-convolution leads to an even more expressive sequence mixing layer.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 to capture long-range dependencies and in-context learning. The data-dependent convolution layer contextually adapts its kernel based on input data using a dedicated conditioning neural network. We design two simple yet effective conditioning networks that maintain shift equivariance in the adaptive convolution 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 O(L log L)) for long sequences. Evaluation across various domains, including language modeling and image classification, presented in section 4 and Appendix, demonstrates the Orchid architecture'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 achievement lays the foundation for further advancements in more efficient and scalable sequence modeling architectures. 
background: 
 Self-Attention Mechanism: Given a length-L sequence of embeddings (tokens) x = (x 1 , x 2 , . . . , x L ), the self-attention layer generates a new sequence by computing a weighted sum of these embeddings. To achieve this, it linearly project x into three components: queries (Q), keys (K), and values (V ), as:Q = xW Q , K = xW K , V = xW V .Each individual attention mechanism within a multi-head self-attention layer operates as a dense linear transformation, expressed as:y = SA(Q, K, V ) = SoftMax QK T √ d k 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 2) and (3) as shift-invariant convolution kernels, are illustrated. In this model, the convolution is performed efficiently in the spectral domain, so the kernel in the frequency domain,h F = h F 0 + h F θ (x), is computed. The block also includes MLPs for linear projection and pointwise mixing of features at the beginning, that is common design choice used in various sequence modeling architectures. long-range dependencies using a sublinear parameter count. The attention mechanism enables direct computation of interactions between any two positions in the input sequence, regardless of their distance, without a corresponding rise in parameter counts. Additionally, the attention layer implements a data-dependent dense linear filter, which effectively filter the input based on on weights conditioned by a mapping of the data. This property makes it expressive and flexible enough to encode a large family of linear functions. However, these advantages come at the expense of quadratic computational complexity and memory costs. This motivates us to develop an efficient and scalable data-dependent convolution mechanism, featuring an adaptive kernel that adjusts based on the input data. The kernel size of this convolution layer is as long as the input sequence length, enabling the capture of long-range dependencies across the input sequence while maintaining high scalability.Linear Convolution: Discrete-time linear convolution is a fundamental operation in digital signal processing that calculates the output as the weighted sum of the finite-length input x with shifted versions of the convolution kernel, h, also known as the impulse response of a linear time-invariant (LTI) system. 2 Formally, it can be written asy[t] = (h * x)[t] ≜ L-1 ℓ=0 h[t -ℓ]x[ℓ].In this definition, the output is a linear filter of the zero-padded input and convolution kernel. However, other padding schemes leads to different forms of convolution. A well-known form is circular convolution, defined asy[t mod L] = (h ⊛ x)[t] ≜ L-1 ℓ=0 h[t -ℓ mod L]x[ℓ],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, explicitly parameterized with a short kernel, struggle to capture long-range dependencies in sequential data. Extending the kernel to 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 parameterized using a multilayer perceptron (MLP), a technique that has been shown to maintain sub-linear parameter scaling [Karami et al., 2019 , Romero et al., 2021 , Li et al., 2022 , Poli et al., 2023] . Furthermore, a key advantage of convolution operators is that, leveraging the convolution theorem, convolution operators can be efficiently computed in the frequency domain using Fast Fourier Transform (FFT) algorithms, thereby reducing the computational complexity to O(L log L) [Cooley and Tukey, 1965] . Formally, the linear convolution can be expressed in the frequency domain as ŷ = F -1 (F( ĥ) ⊙ F( x)) = T -1 (h F ⊙ T x), where T is the DFT matrix, F denotes the discrete Fourier transformation, and x denotes the zero-padded signal, defined as x ≜ pad 2L (x) = [0 L ; x]. Additionally, the circular convolution can be simply computed as:y = h ⊛ x = F -1 (F(h) ⊙ F(x)). 
orchid operator: 
 This section introduces the Data-Dependent Convolution Filter, a 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.We hypothesize that making the convolutional kernel data-dependent allows the filter to adapt to the specific characteristics of its input, potentially capturing more complex patterns within the sequence. Formally, this input-dependent filter is defined as:y = h θ (x) * x = NN θ (x) * x (1)The key innovation is to replace the static convolutional kernel with a conditionally generated one controlled by the input data. This is achieved through a conditioning network, denoted as h θ (x) = NN θ (x), a neural network parameterized by θ. 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 its specific representation. Convolving the surrounding context using this data-dependent weighting scheme can potentially offer more effective sequence mixing compared to conventional static convolutions.A fundamental property of discrete convolution is shift equivariance, meaning that shifting the input by a certain amount leads to a corresponding shift in the output (disregarding boundary effects). This is formally expressed for circular convolution as: shift m (y) = h ⊛ shift m (x) [Bronstein et al., 2021] , where this property holds exactly regardless of boundary conditions. The shift operation is defined asshift m (x)[t] ≜ x[t + m].This property is particularly important because it ensures the operator's response is robust to shift of features within the input, thereby enhancing the model's generalization capabilities. This inductive bias is 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-invariant, i.e. h(shift m (x)) = h(x) (refer to Appendix B for the proof). In the following, we present two conditioning network designs satisfying shiftinvariance.A circular shift of a sequence u results in a linear phase shift of its frequency components:F shift m (u) [ω] = u F [ω] • e -i2πL ωm [Oppenheim, 1999]. Given a shift-equivariant function g(x) (such as a depthwise Conv1d()) (satisfying: g(shift m (x)) = shift m (g(x))). Its frequency components after a spatial shift of its input maintain this phase shift:F g(shift m (x) [ω] = F (g(x)) [ω] • e -i2πL ωm . By taking the magnitude (absolute value or squared) of these complex-valued frequency components, we effectively eliminate the phase shift, therefore, defining h F (x) = F g(x) satisfies shift-invariance property: h F (shift m (x)) = h F (x).In our design, we deploy a hybrid spatial-frequency domain conditioning network. This network consists of a 1D depthwise linear convolution (Conv1d())) with a short kernel length (typically 3-5) acting at the spatial domain, followed by a short convolution in the frequency domain. By operating 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:EQUATION) This architecture choice aims to minimize 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 sequence. Let k(x) and q(x) be two shift-equivariant functions, satisfying: k(shift m (x)) = shift m (k(x)) and q(shift m (x)) = shift m (q(x)). We define h(x) as the cross-correlation of k(x) and q(x), given by:h(x)[t] = (k(x) ⋆ q(x))[t] ≜ L-1 ℓ=0 k(x)[ℓ] • q(x)[t + ℓ mod L].This operation essentially slides q(x) over k(x) and measures their similarity at different offsets. Remarkably, the resulting cross-correlation function, h(x), is also shift invariant:h(shift m (x)) = k(shift m (x)) ⋆ q(shift m (x)) = shift m (k(x)) ⋆ shift m (q(x)) = k(x) ⋆ q(x) = h(x)Furthermore, the convolution theorem enables efficient computation of the cross-correlation in the frequency domain:h F (x) = F (k(x) ⋆ q(x)) = k F * (x) ⊙ q F (x)where k F * denotes the complex conjugate of k F and ⊙ represents element-wise multiplication.Remark 3.1. By setting k(x) = q(x) = g(x), we obtain h F (x) = |g F (x)| 2 , This indicates that the cross-correlation approach generalizes the magnitude-based approach, demonstrating its versatility.Similar to the previous approach, we employ separate 1D depth-wise short convolutions for both k(x) and q(x), followed by another convolution post cross-correlation in the frequency domain. As a result, the conditioning neural network is defined asEQUATIONBoth conditioning functions, as defined in (2) and (3), are illustrated schematically in Figure 2 2) 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 a function of any arbitrary sequence u, leading to a broader definition of data-dependent convolution:y(x, u) = h θ (u) * x = NN θ (u) * xThis definition couples the input sequence x with another sequence u, creating a potential alternative to cross-attention layers in sequence processing tasks. We therefore refer to the proposed layer as "data-dependent" in a more general sense. When dealing with sequences of different lengths, the shorter sequence can be zero-padded to match the length of the longer one. Specifically, assuming x ∈ R L is longer than u ∈ R N (L > N ), we use the zero-padded sequence û = pad L (u) ∈ R L as input to the conditioning network NN θ ( û). Since the long convolution is implemented in the frequency domain, this zero-padding in the time domain translates to interpolation in the frequency domain [Smith, 2008] ensuring that both sequences have frequency components of the same length.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. Mathematically, 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 a location-dependent filtering scheme, we complement the data-dependent convolution with element-wise multiplications, allowing the model to emphasize specific tokens within by assigning higher weights prior to applying the location-invariant convolution. Notably, prior research has demonstrated that a cascade of circulant and diagonal matrices can effectively approximate dense linear layers [Moczulski et al., 2015 , Cheng et al., 2015] . 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 a simple chain of order 1.5, consisting of datadependent convolution sandwiched by two element-wise multiplications:y = (f 2 ⊙ • f * • f 1 ⊙ )(x) where • denotes composition, f * (x) ≜ (h θ (x)+h 0 ) * x, and f i ⊙ (x) ≜ Conv1d(x)⊙x.The Orchid block is 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 complexity of O(L log L). Furthermore, the element-wise multiplications contribute an additional O(L) complexity. Consequently, the overall complexity of the Orchid block scales quasi-linearly with the sequence length, resulting in a total complexity of O(M L log 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.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 in conditional convolution in Appendix B. We also provided the references to relevant theorems and lemmas.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 crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems. • The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
experiments: 
 Our evaluation of Orchid focuses on three different Transformer-based models to evaluate its expressivity 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, aiming 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.5 and C.2. Unless otherwise specified, our experiments adopt the phase supersession (Type I) conditioning network (Equation 2) due to its simpler form. For an overview experimental details, please refer to Appendix C.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., 2022] and in-context learning (ICL) [Garg et al., 2022] , is known as Associative Recall. It involves generating a value from a 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 a model can effectively retrieve the correct value from a 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 a 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: I) 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, detailed in [Romero et al., 2021] . III) Hyena, built upon the CKConv framework by incorporating an additional exponential decay modulation into the implicit convolution process, as detailed in [Poli et al., 2023] . It is further augmented by a multiplication in a chain of order 2.As illustrated in Figure 4 .1 and Tables 4.1 and 4.2, Orchid demonstrates superior expressiveness and outperforms existing long convolution models in associative recall tasks. These tasks become increasingly challenging with shorter sequences and larger vocabulary sizes. This difficulty arises because 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, a 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 Transformerbased models for extensive language modeling, suggesting its potential to enhance performance in natural language processing tasks.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 [Joshi et al., 2020] , and others [Jin et al., 2020] . In our experiments, we 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-diagonal 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 a hidden size of 768, the same dimension and depth as BERT-base. The resulting Orchid-BERT-base have 77M parameters, compared to BERT-base's 110M parameters. We also pretrain Orchid-BERT-large of 254M parameters The results presented in Table 4 .4 and 4.5 demonstrate that Orchid significantly outperforms both the Vision Transformer baseline and long convolution-based models on the CIFAR-10 and ImageNet-1K 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 as image processing tasks. 2021] operate in the spectral domain, applying a dense linear layer or an MLP with a block diagonal linear layer. However, these models do not explicitly model convolution kernel and do not enforce shift-equivariance.Question: 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 conclusions of the paper (regardless of whether the code and data are provided or not)? For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to 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 is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example (a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce 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 authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
related work: 
 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 in these models typically rely on the current token or its local neighbors, preventing them from leveraging the benefits of global convolution for efficient parallelizable training Consequently, they heavily depend on hardware-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 proposed 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 inputdependent 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 foundation 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(L log L) 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 [Fu 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 of sub-quadratic structured matrices that generalizes the DFT and other structures. These matrices are parameterized as products of block-diagonal matrices, offering sub-quadratic computation costs ranging from O(L log L) to O(L 3/2 ). By trading-off computational complexity with FLOP utilization, M2 achieves a hardware-efficient alternative for Transformers.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?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 a 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
discussion and conclusion: 
 In conclusion, our work introduces Orchid, a novel model that addresses some critical challenges of efficiency and scalability in sequence modeling through the innovative use of data-dependent convolution. 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 a data-dependent convolution layer represents a significant step forward, offering a scalable and expressive alternative sequence mixing scheme that adapts its weights to the input data. Through evaluation across multiple domains, including in-context learning, language and image processing tasks, Orchid has demonstrated not only its superior performance over traditional attention-based models but also its generality and scalability. This positions the Orchid model not just as a alternative to existing paradigms but as a potential catalyst for innovation, driving the exploration of novel, efficient, and powerful architectures in artificial intelligence.The superior performance of Orchid compared to traditional transformer-based models raises intriguing questions about the current state and future direction of deep learning architectures. One plausible explanation for our model's effectiveness could be the over-parameterization prevalent in transformer-based models. A growing body of evidence indicates that attention mechanisms, despite their computational complexity, utilize only a 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.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] .Justification: the paper provides a 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 a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [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, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 not 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 or failed experiments that didn't make it into the paper). Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] .Justification: This work doesn't involve data or 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 to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.• Including this information in the supplemental material is fine, but if the main contribution 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 Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Looking ahead, extending our model to 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 to differences in how data-dependent global convolution handle dependencies and sequence generation. 3Furthermore, exploring the capability of Orchid as an efficient alternative to cross-attention layer, employed in sequence-to-sequence models, offers another avenue for research. These considerations open up new possibilities for integrating our model into more advanced foundation models and cross-domain applications.Beyond sequence modeling, the Orchid block, with its input-dependent long convolution, local depthwise linear convolution (Conv1d), and element-wise multiplications, is inherently extendable to multi-dimensional data. While the primary focus of this work was designing an efficient and scalable architecture specifically for sequence modeling, expanding the proposed architecture to include 2D or 3D long convolutional approaches is an interesting future direction.• Environmental Sustainability: The efficiency of Orchid, particularly in terms of computational and energy demands, aligns with the urgent need for environmentally sustainable AI 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 process 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.Notations Brief definition and interpretationx, y, W x ∈ R L and y ∈ R L are input and output sequence of a layer, while matrices are denoted by bold uppercase letters, such as layer weight matrix W .h * x linear convolution:y[t] = (h * x)[t] ≜ L-1 ℓ=0 h[t -ℓ]x[ℓ] h ⊛ x circular convolution: y[t mod L] = (h ⊛ x)[t] ≜ L-1 ℓ=0 h[t -ℓ mod L]x[ℓ] k ⋆ q cross-correlation: h[t] = (k ⋆ q)[t] ≜ L-1 ℓ=0 k[ℓ] • q[t + ℓ mod L] h ⊙ x element-wise multiplication (Hadamard product): y[t] = (h ⊙ x)[t] ≜ h[t] • x[t] shiftm(x) shiftm(x)[t] ≜ x[t + m] F(), F -1 (), TThe forward and inverse discrete Fourier transforms while T represents the DFT matrix.x ). The core of Orchid is a long, data-dependent convolution with an adaptive kernel spanning 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 kernels. On the other hand, the conditioning networks responsible for generating this adaptive kernel operate locally in both the spectral and spatial domains.F x F = F(x) = T x x x ∈ R 2L isComparing 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(x) and query q(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 Conv1D operations in both the spatial and spectral domains. The attention mechanisms calculate the input-dependent attention score matrix A(x) and subsequently compute the output as y = A(x)v. In contrast, Orchid 's conditioning network performs a cross-correlation-a global operation-between k(x) and q(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) operate locally on the inputs, the outer blocks (such as the matrix product in attention, cross-correlation or convolution in Orchid) perform global sequence mixing. This approach ensures fixed (or sublinear) 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 a 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 environmental 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 proposed model's computational efficiency aligns with more environmentally sustainable AI practices by minimizing energy consumption and carbon footprint during training and deployment.Proof for Preserving Shift Equivariance: Given a circular shift invariant filter kernel, whereh θ (x[t + m mod L]) = h θ (x[t]).For a circularly shifted input, the circular convolution can be expressed as:(h θ (shift m (x)) ⊛ shift m (x))[t] = L-1 ℓ=0 h θ (shift m (x)[ℓ]) • shift m (x)[t -ℓ mod L] = L-1 ℓ=0 h θ (x[ℓ + m]) • shift m (x)[t + m -ℓ mod L] = L-1 ℓ=0 h θ (x[ℓ]) • shift m (x)[t + m -ℓ mod L] = y[t + m mod L] = shift m (y)[t]Therefore, if the filter kernel is shift-invariant, the conditional convolution will also be shiftequivariant. ■We used associative recall task to evaluate in-context learning of the proposed model. Given a string of key-value tuples from a random dictionary, this task involves generating a value from a key . For instance, given the input ([a, 1 , b, e, 3 , f ], b), the model is expected to return e, the value associated with the key b. This task assesses whether a model can 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-wise attention scores and then weighting the entire sequence accordingly [47] , they face computational difficulties for very large sequence.The model is composed of 2 Orchid block while each Orchid is composed of a chain of order 1.5, including 2 element-wise multiplications and one data-dependent convolution. The hidden size of all models in this experiments are set to 64. The conditioning network, defined in (2), was used which was composed of a 1D depthwise convolution (Conv1d) in the time domain and a Conv1d in the frequency domain that were applied separately to each feature dimension, both having a kernel of length 3. Only for vocabulary size of 40 with short sequence lengths of 128 we increased the depth to 3 layers of Conv1d in the spatial domain and in the frequency domain.For training, we used Adam optimizer [63] with its standard settings (β 1 = .9, β 2 = .999), and learning rate of 5e-4 with linear warmup schedule in 1000 steps. A weight decay of 0.1 was used as a regularizer. The Orchid models were trained Orchid on a single P100 GPU for small to medium sequence length and on a single V100 GPU for long sequences.To better understand the impact of different model components, we conducted several ablation studies on in-context learning task in section 4.1. First, we evaluated different depthwise linear convolution 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 Conv1D layers in the spatial domain only, and III) Spectral Only: applying two Conv1D layers in the spectral domain only. The results, presented in Figure C .1, demonstrate that the proposed method of operating in both spatial and frequency domains (Equation 2) offers the best performance. This approach effectively mixes information from neighboring tokens in both domains, capturing richer representations. Second, we compared the two conditioning networks for data-dependent convolution defined in Equations 2 and 3. We also evaluated various nonlinearity σ() functions used in the Type II (crosscorrelation) conditioning network:EQUATION)The nonlinearities includes {Tanh(), Sigmoid(), Softsign(), Softshrink(), Identity()}, each applied only to the magnitude of its argument. The results in 2). Orthonormal indicates transforms that utilize orthogonal and normalized bases.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 of 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 Conv1d in time domain and a Conv1d in the frequency domain that were applied separately to each feature dimension, both having a kernel of length 3. For dimension mixing, we also substituted the two dense matrices in the MLP layers with block-diagonal matrices of order 1 with b = 4 blocks [21] and also add a residual long convolution to each Orchid layer, as in [44] .Our BERT-style model, called Orchid-BERT-base, was composed of 12 layers with a hidden size of 768, the same dimension and depth as BERT-base resulting in Orchid-BERT-base having 77M parameters, compared to BERT-base's 110M parameters. We also pre-trained Orchid-BERT-large of 254M parameters with hidden dimensions of 1536 and 12 layers.For pre-training, we used decoupled Adam optimizer with β 1 = .9, β 2 = .98, and learning rate of 8e-4 with linear warmup schedule within first 6% of the steps and then decay with linear rate. A weight decay of 1e-5 is used as a 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-uncased tokenizer. Models were pre-trained on a node of 4xA100 GPUs for 70k steps with batch size of 4096.To evaluate the performance of Orchid-BERT models, we finetuned the pre-trained models on GLUE fine-tuning tasks, comparing them against the baseline models: BERT-base and BERT-large, and the recent long convolution-based models: M2-BERT-base and M2-BERT-large [44] . The fine-tuning process was executed in 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 finetuning small dataset tasks: RTE, MRPC, and STS-B are initialized from the fine-tuned checkpoint of MNLI dataset. Models were fine-tuned on a node of 4xA100 GPUs.In contrast to [44] , 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 perform a thorough search for them. As noted in [53] , hyperparameter search can result in substantial improvements in the performance. In particular for CoLA task, whose results are bellow M2-BERT, we anticipate that fine tuning the parameter will improve its performance. The detailed hyperparameters for each task is reported in We extended the application of Orchid to 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-based models, specifically Hyena-ViT-b [31] and M2-ViT-b [44] . We evaluated the models on two widely used image classification datasets: CIFAR-10 and ImageNet-1K.Each Orchid layer consists of a 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 Conv1d 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-1K, respectively.CIFAR-10: For CIFAR-10, images were transformed into sequences of 4 × 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 (β 1 = .9, β 2 = .999), and learning rate of 3e-4 with linear warmup schedule within first 500 steps. For the experiments on Orchid-s (4 × 4), we tuned base learning rate over (1e-3, 5e-3, 1e-2). A weight decay of 0.05 was used as a regularizer. Orchid was trained on a single P100 GPU for 500 epochs with batch size of 512.We segmented images into patches of 16 × 16 pixels, and we trained a ViT-base architecture featuring 12 Transformer layers and a hidden size of 768. We incorporated a residual long convolution within each Orchid layer and substituted the dense matrices in the MLP layers responsible for feature mixing with block-diagonal matrices of order 1 with b = 4 blocks, reducing their computational complexity and the total model's size.For training, we used Adam optimizer with its standard setting (β 1 = .9, β 2 = .999), and base learning rate of 1e-3 with linear warmup schedule within first 10 epochs and then decay with Cosine schedule. For data augmentation, we adopted the T2T-ViT pipeline [67] , including Random erasing with rate=0.25, CutMix with α=1.0, Mixup with α=0.8, AugMix, and RandAugment with [magnitude=9, magnitude-std=0.5, layers=2]. We trained Orchid on 4xA100 GPUs for 300 epochs and batch size of 1024. [24] where dense matrices in the MLP layers are replaced with block-diagonal matrices. Baseline results are sourced from [44] , and ✘ indicates that the Transformer model could not fit in GPU memory. To evaluate the ability to learn long-range dependencies in real-world time-series data, we conducted 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 duration sampled at 16000 Hz for this task. The performance results shown in Table C .4 highlight that Orchid performs on par with the state-of-the-art model on this long sequence modeling task.To assess the computational efficiency of Orchid, we benchmarked its runtime against both traditional attention layers and the optimized FlashAttention mechanism [68] .The evaluation was conducted on an NVIDIA A100-40GB GPU with models featuring a hidden dimension of 768 and a batch size of 1. The empirical runtime comparisons in Figure C.4 highlights Orchid's high scalability, 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 the standard FFT implementation in PyTorch, and further speed improvements are anticipated with the integration of fused CUDA kernels or FlashFFT [43] . 1 import torch 2 import torch . nn as nn 3 from torch_dct import dct , idct 4 from einops import rearrange • 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 be 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section 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 authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.Notably, state space models, in general, include the recurrent layers such as RNN and LSTM[Hochreiter et al., 1997] as special cases.While generally x represents a sequence of D-dimensional embeddings with length L, all the sequence mixing operators, including data-dependent convolutions, Fourier transforms and depthwise 1D convolutions (Conv1d) are performed along the sequence dimension. Therefore, for clarity and without loss of generality, we assume D = 1 and x ∈ R L . For a full list of notation definition, please refer to Appendix A.Notably, recent works such as[Ding et al., 2023, Bachmann andNagarajan, 2024] show that autoregressive models are not optimal for inference in language models. 


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

Reviews: review: paper_summary: paper_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).
strength_weakness: strength_weakness: - 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.
- 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.
questions: 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?
- 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.

[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.
[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: limitations: Authors sufficiently discussion limitations of their approach.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

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

- Although encouraging, I feel that the empirical section misses many important components that would improve the impact and adoption of Orchid.
  - 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.
  - 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?
  - 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.
  - 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. 
  - 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. 
  - 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.
  - 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?
questions: questions: - Line 27. Please add references.

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

- 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: limitations: The authors clearly state the limitations of the proposed method.

### Conclusion

Whilst 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.
questions: 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.
2. There are at least two [Fu et al., 2023] papers being referenced, which creates confusion.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?
2. 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?
3. Conditioning networks: To improve the understanding of the paper, could the authors provide more details about the two conditioning networks introduced in the manuscript?
4. 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.
5. 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?
6. 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.

Grammatical correction:

- "Moreover, its allows for handling very large sequence lengths that are beyond the limitations of the dense attention layers."
questions: questions: Please address the questions and concerns provided in the Weaknesses section
limitations: limitations: The authors have talked about various limitations of the paper.

Comments: title: Updated Results on CIFAR-10
comment: Dear authors,

Thank you for your answer.

**Local conditioning network on spatial and spectral.** That is a good analogy. Thank you for the clarification. It would perhaps be nice to add a section on the appendix explaining this connection. This will probably help readers with doubts about that conditioning part --like myself--, get a better understanding of its relation to self attention.

**Model Architecture in Figure 2.1.** I understand. Could you please add an additional image to the Appendix following those traditional standards to complement the paper? I feel that this still would add much clarify to the paper. 

Under the understanding that the authors will add these two parts to the paper I am happy to increase my score. It is now 7.
Dear Reviewer,


Thank you for your response. Regarding your questions:

-  *Local conditioning network on spatial and spectral:*
   - To address your question, let's clarify this with an analogy. In the conditioning network of Orchid, the pair of signals $ k(x) $ and $ q(x) $ are analogous to the key $ k(x) $ and query $ q(x) $ in the attention mechanism. In both Orchid and the attention mechanism, these components are modeled using local neural networks: attention utilizes pointwise linear projections, while Orchid employs local $ Conv1D $ operations in both the spatial and spectral domains.  
Once $ k(x) $ and $ q(x) $ are computed, attention mechanisms calculate the input-dependent attention score matrix $ A(x) $ and subsequently compute the output as $ y = A(x) v $. In contrast, Orchid’s conditioning network performs a cross-correlation— a global operation—between $ k(x) $ and $ q(x) $ to derive the convolution kernel $ h(x) $, followed by global convolution $ y = h(x) * v $.  
Thus, while the inner blocks (the input-dependent networks that compute the convolution kernel in Orchid or the attention matrix in attention mechanisms) operate locally on the inputs, the outer blocks (such as the matrix product in attention, cross-correlation or convolution in Orchid) perform global sequence mixing. This approach ensures fixed (or sublinear) parameter scaling with respect to sequence length, preventing the model size from growing excessively with sequence length.  
This analogy also applies to Type I, as it is a special case of Type II where $k(x)=q(x)$.

   - Although it is mentioned in line 148-150 that the conditioning network acts on both local spatial and spectral components, we will add this discussion in the final version to prevent potential misunderstandings.

-  *Experimental results on Type II:*  
By including discussions on Type II conditioning  and the Cross-Attention alternative we aimed to highlight and clarify the distinct features of the data-dependent global convolution mechanism in Orchid. We believe that these discussions provide valuable insights that help better understand the architectural design of Orchid and also foster further exploration and innovation in the field by adopting it in other applications by the researchers.  
Moreover, we have conducted experimental evaluations using Orchid with the Type II conditioning network. The results, which are shared in the "official comment" titled *Updated Results on CIFAR-10*, demonstrate a slight improvement in accuracy on CIFAR-10, supporting the potential benefits of this approach.  

-  *Model Architecture in Figure 2.1:*  
The paragraph in our rebuttal starting with “The role of MLPs at the beginning of the block” was intended to address your concerns about this figure. The MLPs at the beginning of the Orchid block are indeed pointwise feature mixing components, a design choice commonly seen in various architectures such as Hyena, M2, and SSM. However, the primary focus of our paper is on sequence modeling using the data-dependent global convolution mechanism.  
The current illustration style in Figure 2.1 was chosen to best represent the distinct features of the Orchid block, particularly highlighting its global convolution mechanism. Such style has been adopted in other relevant models, such as M2 and Mamba which we believe is suitable for our purposes.


Thank you once again for your valuable feedback, and we hope our response has addressed all your questions.
Dear Reviewer,

Thank you for your valuable feedback. We appreciate your suggestion and have included additional results in our "official comment" titled *Updated Results on CIFAR-10*, where Orchid is compared against other models, including CKConv and CCNN. In the original submission, our primary focus was on comparing Orchid with Vision Transformer (ViT) baseline models.

We hope our response has addressed all your questions.
Dear Reviewers,

In response to the feedback, we are including additional experimental results on the CIFAR-10 dataset, complementing the results presented in the paper. For these experiments, the images were converted into sequences using patches of sizes $(4 \times 4)$, $(2 \times 2)$, or $(1 \times 1)$ pixels. We designed Orchid-based models using a ViT architecture composed of 6 Transformer layers, with hidden sizes of either 128 and 220 for Orchid-ViT-s and Orchid-ViT-m, respectively.

**Table RBTL1:** Test performance on the CIFAR-10 dataset flattened with patch sizes $(4 \times 4) $, $(2 \times 2) $, and $(1 \times 1 )$ (sCIFAR). Orchid-ViT-s (Orchid-ViT-m) refers to the ViT architecture composed of 6 layers with hidden sizes of 128 (220). Baseline results are referenced from [1] and [2]. For this result on Orchid-ViT-s  (4 \times 4), we tuned base learning rate over (1e-3, 5e-3, 1e-2).
| **Model (Patch Size)** | **Size** | **Accuracy (%)** |
|------------------------|----------|------------------|
| **ViT** $(4 \times 4)$  | 1.2M	| 78.6         	|
| **ViT+Monarch** $(4 \times 4)$ | 607K	| 79.0         	|
| **Hyena-ViT** $(4 \times 4)$  | 1.3M	| 80.6         	|
| **M2-ViT** $(4 \times 4)$  | 741K	| 80.8         	|
| **Orchid-ViT-s** $(4 \times 4)$  | 735K	| 88.5    	|
|------------------------|----------|------------------|
| **CKConv** $(1 \times 1)$  | 1M  	| 63.74        	|
| **M2-ViT** $(1 \times 1)$  | 741K	| 91.0         	|
| **S4** $(1 \times 1)$  | 7.8M	| 91.13        	|
| **CCNN** $(1 \times 1)$  | 2M  	| 93.08        	|
|------------------------|----------|------------------|
| **Orchid-ViT-s** $(2 \times 2)$  | 790K	| 92.2         	|
| **Orchid-ViT-s  Type II** $(2 \times 2)$ | 799K	| 92.3         	|
| **Orchid-ViT-m** $(2 \times 2)$  | 2.1M	| **93.33**    	|
| **Orchid-ViT-m** $(1 \times 1)$  | 2 M	| 93.0   	|

**Key observations from this empirical study:**
- Orchid outperforms baseline models on the CIFAR-10 dataset.
- Using smaller image patches can boost the performance.
- The Type II conditioning network offers a slight improvement in accuracy on Orchid-ViT-s.

[1] Daniel Y Fu, et al. Monarch mixer: A simple sub-quadratic GEMM-based architecture. arXiv preprint arXiv:2310.12109, 2023.  
[2] Knigge, D. M., et al. Modelling Long Range Dependencies in D: From Task-Specific to a General Purpose CNN. arXiv preprint arXiv:2301.10540, 2023.
Dear authors,

Thank you so much for your response. 

My questions regarding the experimental section have been answered. However, multiple questions that remain open / unanswered:

*While 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*

+-> It is clear to me that the input is mixed across the entire sequence. However, as indicated before, the conditioning is local. This should be made clear in the paper as this elucidates improvements that can be done to the method in the future.

Regarding **questions**:

* Respectfully, I am strongly against that kind of "flag planting" that is made in the paper for both the Type II conditioning as well as for the Cross-Attention alternative. I believe that only things that are used in the paper *should* be included. I believe that this hinders progress on the field, as other researchers --or even yourself-- might feel that contributing and experimenting with those parts are not worth pursuing, as it has already "been done before" (which is not the case). I would strongly encourage the authors to remove the parts that are not used in the model.

* There is no rebuttal PDF attached anywhere.

* The authors did not answer my comment regarding Figure 2.1. I would encourage the authors to improve this image as it is the main image of the paper. It would aid clarity to use the conventional way of illustrating network blocks, as has been done in several papers before, eg., ResNet, Transformer, etc.

Due to the observations outlined before, I am not compelled to support a clear acceptance. I therefore will maintain my score.



   






Unfortunately, I am unsatisfied by your rebuttal response.
- *Associative Recall on SSM-Based Models:*   
In the following table, we compare the performance of Orchid against other long convolution models and an input-dependent SSM (Mamba) on the associative recall task. As the results indicate, Orchid achieves state-of-the-art performance among existing scalable sequence models for this task.

**Table AR2:** This table presents the test accuracy (in %) of in-context learning on the associative recall task with a sequence length of 128 and varying vocabulary sizes.

| Vocabulary Size | 20   | 30	| 40	|
|-----------------|------|-------|-------|
| **Transformer** | 100  | 100   | 100   |
| **CKConv**  	| 91   | 25.7  | 20.4  |
| **H3**      	| 71.5 | 13.2  | 10.2  |
| **Hyena**   	| 93   | 38.8  | 12.4  |
| **Mamba**   	| 100  | 100   | 35.8  |
| **Orchid**  	| 100  | 99.4   | 99.2  |

- *Expanding Orchid to 2D long convolution long:*  
The Orchid block, with its input-dependent long convolution, local depthwise linear convolution (Conv1d), and element-wise multiplications, is inherently extendable to multi-dimensional data.
However, our primary focus in this work was on designing an efficient and scalable architecture specifically for *sequence modeling*. Expanding our architecture to include 2D-convolutional long-range approaches, while valuable, was beyond the scope of our current study and is an interesting future work.


**UPDATE**
- We appreciate your suggestion and have included additional results in our "official comment" titled [*Updated Results on CIFAR-10*](https://openreview.net/forum?id=a75F45dBHK&noteId=h2L7DEaIKv), where Orchid is compared against other high-performance models. As the results show, using smaller image patches boosts the performance. Additionally, we include results for Orchid with the Type II conditioning network, which offers a slight improvement in accuracy on CIFAR-10.
I would like to thank the authors for their detailed response. Additional ablation studies and experimental results with a large (16k) sequence length help alleviate some of my concerns related to method performance. However, the fact that the proposed technique cannot be applied to causal models can still be seen as a limiting factor for its applicability. The authors cited several papers highlighting the limitations of the autoregressive modeling approach, however these types of models still appear to be the golden standard in numerous practical applications. It is also worth mentioning that some of the mentioned papers, are either considering very specific setups (in-context learning setups with the full attention over the context component), or propose to alleviate the limitations of next-token prediction models using modifications within the same causal setup. Considering concerns raised by other reviewers and the authors replies, I would like to keep my current favorable score.
I thank the authors for their response. Most my concerns have been answered, except for the seemingly arbitrary choice by the authors to compare against ckconv in one experiment but not in another experiment where it is outperformed by CKConv. I would recommend adding these results.
Thank you for your detailed review and valuable feedback. Your recognition of the contributions of the proposed Orchid architecture and the comprehensive empirical evaluations and also your valuable feedback is appreciated. In the following, we address the points you raised in your review.


- *W1: Citation issue at page 3:*
Thank you for bringing this to our attention. We will ensure that this issue will be fixed.


- *W2: Computational Complexity of Conditioning Networks*  
We designed simple conditioning networks using $Conv1d()$ (1D depthwise linear convolution with a short kernel length, typically 3-5) in both the spatial and frequency domains. This architecture choice aims to minimize the number of parameters and computational overhead of the conditioning networks. As a result, the number of parameters does not grow with the sequence length. The computational complexity of $Conv1d()$ is $\mathcal{O}(L D)$, which scales linearly with the sequence length, while FFT computations scale quasilinearly with the sequence length ($\mathcal{O}(L \log L)$).  
It's worth noting that computing the projections for $K$, $Q$, and $V$ in transformers requires $\mathcal{O}(L D^2)$ computation. The runtime benchmarks provided in Appendix C.6 demonstrate the speed performance of Orchid compared to Attention and FlashAttention, highlighting its efficiency.

- *W3: More Details on the Two Conditioning Networks*  
To model the convolution kernels dynamically as a function of the input, we designed two simple conditioning networks that maintain shift equivariance. We chose architectures that minimize parameters and computational overhead while being efficient.  
   - *Conditioning Network I (Equation 2)*: This network first applies a short convolution $Conv1d()$ on the sequence, then transforms the signal into the spectral domain using the Fast Fourier Transform (FFT). Then an absolute value is applied to preserve shift invariance of the kernel.  
Another short convolution $Conv1d()$ is then applied in the spectral domain. This combination of spatial and frequency domain filters effectively captures information from local neighboring tokens and spectral components.  
   - *Conditioning Network II (Equation 3)*: This network first applies two short convolutions $Conv1d()$ on the sequence to obtain two versions of the input sequences, $k'(x)$ and $q'(x)$. Similar to the previous approach, the signal is then transformed into the spectral domain and pointwise multiplied (to implement a fast cross-correlation). Finally, another short convolution $Conv1d()$ is applied in the spectral domain. This approach generalizes Conditioning Network I.   
Both of these conditioning functions are illustrated schematically in Figure 2.1. The output from these conditioning networks is used as the kernel of the long data-dependent convolution that globally mixes the sequence.


- *W4: Conditioning Network Used in Experiments*  
We used Conditioning Network I for the experiments presented in the paper, as mentioned in Section C.2 of the Appendix (Experimental Details). Conditioning Network I is slightly more efficient in terms of speed and parameter counts. Based on the ablation study in the appendix, we selected Conditioning Network I for the language, vision, and audio experiments reported in the paper. We will add this clarification to the main body of the paper to ensure readers better understand the experimental setup and results for this selcetion.

- *W5: Impact of using Block-diagonal weights in MLP blocks:*    
Indeed 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 can be attributed to the data-dependent sequence mixing mechanism. 
Using 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.
Thank you for your detailed and thoughtful review of our paper. We appreciate your recognition of the contributions and the strengths of our paper. In the following, we address your points.



- *W1:* 
Although the current form of the Orchid is not compatible with causal and autoregressive models, since it uses the entire sequence as context, but this property makes it particularly suitable for encoder-based models like BERT and scalable candidate for diffusion models such as [1]. However, it is worth noting that recent studies [2, 3] have raised questions about the optimality of autoregressive models for inference in language models.

- *W2:* 
For sequence of length, we have also evaluated the performance of the proposed method on a raw audio dataset with a large sequence of length 16k in Appendix C.5. While the standard Transformer model could not fit in GPU, Orchid performs on par with the state-of-the-art model on this long sequence modeling task.

- *W3:*
In addition to the ablation studies presented in Appendix C.2, we have conducted further ablation studies on the conditioning network architecture on associative recall task:

   - Comparison of Local Conv1D Choices: We evaluated different short depthwise linear convolution architectures in the conditioning network, as outlined in Equation (2). This ablation study compared: I) applying Conv1D() in the spatial domain followed by Conv1D() in the frequency domain (as proposed in Equation (2)), II) applying two layers of Conv1D() in the spatial domain only, and III) pplying two layers of Conv1D() in the spectral domain only. The results demonstrated that the proposed method of operating in both spatial and frequency domains (as in Equation (2)) which mixes information from neighboring tokens and spectral token shows the best performance.

   - Impact of Different Nonlinear $\sigma()$ Functions: We evaluated various nonlinear $\sigma()$ functions used in the Type II (cross-correlation) conditioning network (Equation (3)). The nonlinearities tested included \[ Tanh(), Sigmoid(), Softsign(), and Softshrink(), Identity()\], all acting on the magnitude of the argument. The results indicated that dropping this nonlinearity, $\sigma()$ in Equation (3), provides the best performance which is slightly better than nn.Softshrink() and nn.Tanh(). Also, among the nonlinearities those that cross zero perform better. 
Moreover, we also observe that Type II conditioning networks with Identity() and Softshrink() have faster convergence than Type I. 

**Questions:**    


- **Q1: Applying Nonlinearity on the Magnitude in Type II Conditioning Network to Preserve Shift-Equivariance**  
Thank you for your insightful question. As you correctly noted and also mentioned in the paper, 
each of K and Q should remain shift (translation) equivariant, in order that their cross-correlation satisfies the shift-invariance property for the conditioning network. Threfore the nonlinearity $\sigma()$ in Equation (3) should act on the magnitude of the argument while preserving the phase. This approach ensures that each of \( K \) and \( Q \) remains shift-equivariant.
However, as mentioned in our new ablation study on the associative recall task, we found that dropping this nonlinearity yielded the best performance. We will include this clarification in the final version of the paper.


- **Q2: Duplicate References to [Fu et al., 2023]**  
Thank you for bringing this to our attention. We will ensure that this duplicate reference will be fixed.


[1] Lou, Aaron, Chenlin Meng, and Stefano Ermon. "Discrete diffusion modeling by estimating the ratios of the data distribution." ICML (2024)  
[2] Nan Ding, Tomer Levinboim, Jialin Wu, Sebastian Goodman, and Radu Soricut. Causal lm is
not optimal for in-context learning. arXiv preprint arXiv:2308.06912, 2023.  
[3] Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction. arXiv preprint arXiv:2403.06963, 2024.