Orchid: Flexible and Data-Dependent Convolution for Sequence Modeling

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.

Thank you for your constructive feedback on our paper. We appreciate your recognition of the novelty and soundness of our approach, as well as the compelling empirical evidence. In the following, we address the points you raised in your review.

• Orchid is using local info for spectral and spatial:
  In the proposed method, the long data-dependent convolution has an adaptive kernel that spans the entire length of the input sequence. This means that the convolution operation performed by Orchid indeed mixes the entire sequence globally using the proposed adaptive input dependent kernels, rather than being restricted to local windows. 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,

• The role of MLPs at the beginning of the block:
  The MLPs included at the beginning of the Orchid block serve as feature (dimension) mixing components that are commonly used in various sequence modeling architectures, such as Hyena, M2, and SSM. In practice, these MLPs perform a pointwise mixing of features, which is a standard technique employed both before and after sequence modeling operations in architectures like transformers. Since the main focus of our paper is on sequence modeling using the data-dependent global convolution mechanism the text focused on these parts in detail. However, we will clarify the role of these MLPs in the final version.

• Impact of using M2-MLP blocks on the final results:
  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 are 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

Questions:

• Q1: reference for line 27 Thank you for pointing this out. We will add the references to support the statements such as [1]

• Q2: Why Type II is introduced in the text? The Type II (cross-correlation) approach generalizes the Type I (magnitude-based) approach and encompasses it as a special case. The introduction of Type II was intended to provide a more comprehensive view of the conditioning techniques available. Moreover, recent ablation studies, detailed in the rebuttal PDF, indicate that Type II combined with DCT performs better than Type I with DCT. However, since it is slightly more efficient in speed and parameter counts, Type I with DCT was selected for the in language, vision and audio experiments reported in our paper

• Q3: Cross-attention functionality of Orchid:
  In the text we emphasize the novel capabilities of the Orchid model. The other long convolution based methods, such as Hyena and M2, and SSM-based methods such as Mamba, are not inherently applicable as an alternative to Cross-attention, so in this work we emphasize that the Orchid model is not only input-dependent but also its kernel can be conditioned on the an arbitrary input of any length so we call it data-dependent to infer more general than input-dependent modules. Implementing this ability of the proposed model could be a valuable direction for future work.

[1] Nguyen, Eric, et al. "Hyenadna: Long-range genomic sequence modeling at single nucleotide resolution." Advances in neural information processing systems 36 (2024).

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

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

Thank you for your thoughtful review and valuable feedback. We appreciate your recognition of the contributions and the strengths of our paper. In the following, the points you raised in your review are addressed.

• W1: Compare against 2D-convolutional long-range approaches:
  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 comparisons to include 2D-convolutional long-range approaches, while valuable, was beyond the scope of our current study and is an interesting future work.
  Regarding your point on the limited set of experiments against baselines, Appendix C5 also explores the ability of Orchid to learn long-range dependencies in speech classification tasks with long sequences. In these experiments, we compared Orchid against CKConv, Performer, and SSM-based models.

• W2: Absolute positioning in a sentence might impact semantic meaning:
  Our approach to shift invariance focuses on preserving the relational positions of tokens. While changing the order of the tokens/words and their absolute positioning might impact the semantic meaning, we expect that if an entire sentence is shifted and pad tokens are appended before or after it, the sequence retains its semantic meaning. Indeed the relational positions of the tokens remain consistent in such cases.
  Furthermore, the positional embeddings added to the token embeddings, at the beginning of language models, encode the absolute positions of the tokens, enabling the model to generate semantic differences when the order is changed. Moreover, ​​to achieve a location-dependent filtering scheme, we complement the data-dependent convolution with element-wise multiplications which allows the model to emphasize specific tokens in a sequence.

• Q1: Why are shorter sequences more challenging in the in-context learning task?
  Shorter sequences pose a unique challenge in in-context learning tasks because specific (key, value) pairs appear less frequently within the string. This reduced frequency means the model has fewer opportunities to learn and generalize these associations. Additionally, when the vocabulary size also increases, the task becomes even more challenging for the model. The combination of infrequent pair repetitions and a larger vocabulary require a more expressive model architecture to effectively capture and utilize these (key, value) pairs within shorter sequences.

• Q2: Compare against CKConv variants:
  Fixed long convolution kernel term (bias term) in Orchid and also convolution kernel in Hyena and M2 model are built upon long convolution kernel in CKConv, so by comparing against Hyena and M2 we explore the impact of the proposed input-dependent convolution that was introduced by Orchid model. Moreover, in speech classification tasks with raw speech, Orchid is compared against CKConv.