We thank the reviewer for supporting the acceptance of our paper and appreciating our thorough evaluation and analysis. We address the reviewer's only question below:

Runtime Comparison

Please see our Author's rebuttal at the top of the page and the attached pdf. Our results show that MRConv is substantially faster than the efficient FlashAttention implementation, particularly for long sequences. Furthermore, our results emphasize that even our non-reparameterized kernels are efficient and remain computationally faster than FlashAttention, aligning with our theoretical complexity calculations.

We appreciate the reviewer's useful feedback and address their weaknesses and questions below. We hope this resolves any of the outstanding concerns.

1. Results on NLP

Although NLP is an important area of study, we have yet to explore the application of MRConv in its current form to language modelling. Previous purely convolutional methods, such as S4, have struggled to outperform attention-based architectures without additional input dependencies, such as gating used in Hyena and H3 or attention in MEGA. Additionally, [1] has theoretically proven that non-input-dependent gated convolutions cannot solve multi-query associate recall tasks without the hidden state dimension scaling linearly with the sequence length. As a result, we view the paper's contributions in training and structuring long convolution kernels as a promising initial step toward language modelling. We believe that designing input-dependent architectures that leverage multi-resolution convolutions for NLP presents a promising future research direction.

2. Efficiency Benchmarking

When comparing FLOPs between different models, it's crucial to consider all computations to compare models with different architectures, such as the Swin transformer, which uses patching and self-attention rather than convolutions. Isolating only the convolution layer would render such comparisons challenging. Furthermore, when comparing FLOPs between ConvNeXt and MRConvNeXt, given both use an identical ConvNeXt backbone, the only discrepancy in FLOPs arises from altering the convolutional layers. Hence, we think it is intuitive how our 1D convolutions reduce the number of FLOPs compared to 2D convolutions.

3. Runtime Comparison

Please see our Author's rebuttal at the top of the page and the attached PDF. Our results show that MRConv is substantially faster than FlashAttention. We note that MRConv, SGConv, Conv1D are all equivalent to a global convolution and hence runtimes are identical once the kernel has been computed and cached. Table 4 in our paper presents further runtime comparison, for which MRConv is 1.5 and 1.3 times faster than S4 on ListOps and Image tasks.

4. Normalized parameter counts

Throughout our evaluation, we deliberately choose to focus on equating computational complexity between different models rather than parameter counts. For example, in Table 2, although each design ablation has a different number of parameters, each model maintains identical computational complexity, corresponding to a model with a fixed width and fixed number of global convolution layers. We find this to be a more natural point of comparison, which is more correlated with practical performance.

5. Additional ablation studies

We want to thank the reviewer for their valuable suggestions. We have followed the reviewer's guidance and conducted the additional ablations which we will include in our camera-ready paper.

5.1 Initial resolution

We find that the initial resolution is an important hyperparameter that determines the number of resolutions but also performance on different data modalities. As a result, we provide additional ablation studies on the ListOps and Image LRA tasks where we vary the initial kernel size.

|Initial Kernel Size|Num Resolutions|Accuracy| |-----|-----|-----| Listops - Fourier Kernel |1|11|61.80| |2|10|62.40| |4|9|61.10| |8|8|60.95| Cifar - Fourier Kernel |8|8|86.69| |16|7|88.39| |32|6|88.55|

5.2 Decay factor

A key factor of our work is that we don't use a fixed decay factor but that we learn one implicitly by learning the weighted sum of multi-resolution kernels. In Table 2, we show that learning the weighted sum of kernels improved performance over dense kernels by 3.9% and 3.75% on the ListOps and Image tasks respectively.

5.3 LayerNorm

LayerNorm is not amenable to structural reparameterization as it remains a nonlinear operation at inference and hence we don't consider it to normalize each multi-resolution convolution.

5.4 Initialization

A key advantage of MRConv is its simple initialization of convolution kernels, unlike S4 and S4D which require intricate HiPPO theory to initialize them correctly.

6. Insights on MRConv

In Section 5.1 'Resolution Analysis' we analyse the inductive bias of MRConv to learn different frequency kernels at different layers in the network. This is an inductive bias driven by our multi-resolution framework and ability to implicitly learn the decay rate via the weighted sum of kernels. Further in Section 5.1 'MRConv Design' we perform a detailed ablation study showing how each component of our multiresolution framework improves performance. In particular, we highlight the importance of BatchNorm and how normalizing the activations from each convolution before summing is imperative to performance. We also include additional convergence plots to accompany these ablations in our author rebuttal which further emphasize how our design features enable faster convergence and better generalisation by preventing overfitting. We will make sure to include a summary of our insights in the revised paper.

7. Focus of the paper

We thank the reviewer for raising this point and clarify our motivation. The motivation for our work is to parameterize global convolution kernels such that they have the correct inductive biases for long sequence modelling. Indeed, the biggest problem with using convolutions for long sequence modelling is overfitting and we show that our parameterization not only provides stable training (see additional convergence plots in author rebuttal) but also learns to prioritize local information (Figure 3 in paper) equipping our kernels with the right inductive bias to make them highly effective on long sequence modelling tasks. We will make sure to highlight this fully in our revised paper!

[1] Arora, Simran, et al. "Zoology: Measuring and improving recall in efficient language models." 2023

We thank the reviewer for their support of our paper and their insightful feedback which leaves plenty of room for future work. Below we answer the questions raised by the reviewer.

1. Comparison with SSMs

As mentioned in our introduction, SSMs such as S4 and S4D can be represented equivalently as a global convolution, with the kernel implicitly parameterized by the SSM system matrices (refer to Equation 3). Hence, in theory, SSMs and global convolution methods like MRConv perform the same operation. Therefore, differences in expressivity depend on how different methods implicitly parameterize the convolution kernel: SSMs do so via system matrices, while MRConv does so through the weighted combination of multi-resolution kernels. Under certain parameterizations, we establish a direct theoretical equivalence between SSMs and Fourier kernels, where the SSM parameters define a kernel as the weighted sum of truncated Fourier basis functions (see Appendix B.3). However, it is not immediately clear how to reparameterize multi-resolution SSMs when computed in recurrent form. Generally, measuring the expressivity of different convolution kernels is a non-trivial task. Consequently, we evaluate expressivity based on empirical results from benchmark tasks, and our findings indicate that MRConv outperforms S4 and SGConv on LRA, sCIFAR, and Speech Commands.

2. BatchNorm

We incorporate BatchNorm primarily for 2 reasons

2.1 Preserve Variance

Firstly we use BatchNorm to ensure that the variance of the output from each convolution remains consistent regardless of the kernel length. We find this is crucial for learning the weighted sum of kernels. Indeed, the addition of BatchNorm significantly enhances performance, as evidenced in Table 2 of the paper, and accelerates convergence, as illustrated in our new convergence plots in our one-page attachment in the author's rebuttal. We note that other types of normalization, such as LayerNorm, remain non-linear during inference and therefore are not amenable to structural reparameterization unlike BatchNorm.

2.2 Diversify Optimization

Further, BatchNorm is also used to diversify optimization by introducing training-time non-linearity by dividing the output of each convolution by its standard deviation [1]. Consequently, during backpropagation, we compute gradients which cannot be calculated by differentiating a global kernel that has already undergone reparameterization. We provide an extra ablation study where we replace BatchNorm with normalization by a constant factor, computed as the norm of the kernel over the sequence length at initialization. Our results highlight that while normalization by a constant factor improves performance compared to no normalization, it still falls short of the benefits of using BatchNorm.

ListOps - Fourier Kernel |Norm Type|Accuracy| |-----|-----| |BatchNorm|62.40| |$1/\|k\|$|61.05|

Image - Fourier Kernel |Norm Type|Accuracy| |-----|-----| |BatchNorm|89.30| |$1/\|k\|$|87.72|

3. Typo

We would like to thank the reviewer for bringing this to our attention. In this context, the parameter $k$ denotes the number of non-zero elements in the dilated convolution kernel. In the final version, we will rectify the error and clarify the text. Thank you once again for identifying this oversight!

4. Reparameterization via Gating

This suggestion is excellent. Firstly, we found that linear rescaling works well when reparameterizing multiple kernels of the same length (see Section 3.1), eliminating the need for BatchNorm. This allows us to reparameterize many different kernels with differing parameterizations during training at no extra cost. Our initial investigations combining both Fourier and Sparse kernels suggest that this is a highly effective parameterization, delivering competitive results on LRA and ImageNet classification. Secondly, while we currently learn a fixed set of weights to linearly combine each kernel, gating could be a highly effective method for combining kernels in an input-dependent manner. We believe this could effectively introduce input dependency into our model, potentially aiding the application of MRConv to more complex data modalities, such as text. We leave this suggestion for future work but thank the reviewer for their inspiring comment!

[1] Ding, Xiaohan, et al. "Repvgg: Making vgg-style convnets great again." 2021.

Thank you for your overall supportive review of our work. The reviewer asked several insightful and detailed questions about our proposed method, which we will respond to in order.

1. Complexity analysis

We agree with the reviewer that, compared to inference complexity, our training complexity is more costly. However, we do not see this as a limitation of our method because: i) it is more important to have lower inference complexity than training complexity in practical applications and ii) our training complexity is still considerably more efficient than self-attention in theory. In light of the reviewer's comments, we show that a complexity analysis highlights the theoretical benefits of our model regarding training and inference complexity. Assuming we have $\log_2(L/l_0)$ resolutions, the computational complexity during training to compute the convolutions is $\mathcal{O}(L \log_2(L/l_0) \log_2(L))$. In the most computationally demanding setting where the initial resolution $l_0=1$ the computational cost during training is $\mathcal{O}(L \log_2^2(L))$, which is subquadratic wrt. sequence length. Hence, even when training individual kernels in parallel, our model is theoretically more efficient than self-attention mechanisms, which scale quadratically with sequence length during training. In the camera-ready version, we will add this complexity analysis and a more detailed discussion of the computational costs incurred during training.

2. Runtime Comparison

Please see our Author's rebuttal at the top of the page and the attached pdf. Our results show that even our non-reparameterized kernels are efficient and remain computationally faster than FlashAttention, aligning with our theoretical complexity calculations

3. Decay Filters

Ablations on LRA wrt. decay filters can be found in Table 1.

4. Use of BatchNorm

BatchNorm serves multiple purposes in our parameterization.

4.1 Preserve Variance

Firstly, it ensures that the variance of the output of each convolution equals that of the input, improving performance, as evidenced in our design ablations in Table 2 and accelerating convergence, as illustrated in our new convergence plots in our one-page attachment in the author's rebuttal

4.2 Diversify Optimization

Secondly, BatchNorm diversifies optimization dynamics by introducing additional training-time non-linearity, leading to gradients that cannot be replicated by an equivalently reparameterized kernel [1]. In response to the reviewer's suggestion, we conducted an additional ablation study, substituting BatchNorm with normalization by a constant factor, computed as the norm of the kernel over the sequence length at initialization. Our results indicate that while normalization by a constant factor improves performance compared to no normalization, it still falls short of the benefits of using BatchNorm. Nonetheless, this presents a promising research avenue, and we appreciate the reviewer for their valuable input!

ListOps - Fourier Kernel |Norm Type|Accuracy| |-----|-----| |BatchNorm|62.40| |$1/\|k\|$|61.05|

Image - Fourier Kernel |Norm Type|Accuracy| |-----|-----| |BatchNorm|89.30| |$1/\|k\|$|87.72|

5. Combining kernels in the Fourier space

Combining the kernels in the Fourier space to avoid excessive FFTs is an attractive proposition. However, a key challenge arises from the fact that each multiresolution kernel has a different length, which means that each kernel is defined by an inverse FFT of different length. As a result, it's not straightforward to parameterize all kernels in a single Fourier basis defined over the longest kernel length. We also note, that even in our current parameterization we only require a single FFT of the input, as it is reused in each multi-resolution convolution.

6. Implicit kernel parameterizations

This is a very interesting question and boils down to what is meant by expressivity of parameterization. In our work we base expressivity on 2 factors: i) the number of parameters used to define the kernel; the number of Fourier modes or the number of non-zero values in the sparse parameterizations and ii) the kernels inductive bias; Fourier kernels are very smooth whereas dilated kernels are very rough. We choose to focus on the kernels inductive bias and show that different kernels perform better on different data modalities (see Section 5.1 'Kernel parameterization'). As suggested we ran an extra ablation study where we parameterize the kernel as a small MLP as used in CKConv and Hyena. Our results show that the inductive biases of the Fourier and dilated kernels are better suited to the ListOps and Image tasks in the LRA benchmark. It would be very interesting to consider different implicit parameterizations in future work.

ListOps |Kernel Type|Params|Accuracy| |---|---|---| |Dilated|759K|59.25| |Fourier|332K|62.40| |Fourier+Sparse|420K|62.25| |MLP|580K|60.08| Image |Kernel Type|Params|Accuracy| |---|---|---| |Dilated|3.5 M|90.37| |Fourier|3.8M|88.55| |Fourier+Sparse|4.0M|89.07| |MLP|3.6 M|85.71|

7. Learnable Summation

The parameter $\alpha$ represents the weight assigned to each convolution kernel before summation. Upon reviewing equations 12 and 13 in the paper, it appears that the reviewer may have misconstrued $k_i$ as the first element of some kernel $k$, when in fact $k_i$ corresponds to the convolution kernel of length $l_i$ at resolution $i. Consequently, **$\alpha_i$does indeed influence the decay rate** of the reparameterized kernel. Generally, **larger values of$\alpha$ are associated with shorter kernels**, while smaller values are associated with longer ones, as demonstrated in our ablation study in Figure 3. This effect is evident in Figure 5, where we visualize the kernels learned in our ImageNet experiments.

[1] Ding, Xiaohan, et al. "Repvgg: Making vgg-style convnets great again." 2021.

Dear authors,

Thank you very much for your reply and additional experiments. I am looking forward to your future work. Hopefully these suggestions will help in creating a faster MRConv version in the future.

I understand your point about the method being faster than Transformers. But I'd still argue that the method can become, for example, dramatically slower than 1 resolution methods, specially during training. I do not think that this "deficiency" is a deal breaker in terms of the value and possible impact of the paper. However, I do think that making this very clear is important.

Under the promise that the authors will make the limitations of the paper clear in the final version of the paper, I am happy to support acceptance. Under this promise, I have now increased my score to 7.

We thank the reviewer for pointing out several points of inclarity in the existing manuscript, which we seek to address below:

1. Novelty of MRConv

Whilst structural reparameterization has been used in computer vision, we believe that its application in long-sequence modelling has not yet been effectively demonstrated. Therefore, our primary motivation is to adapt structural reparameterization for effective long-sequence modelling. Specifically, we want to highlight key novelties between MRConv and previous methods.

1.1 Linear Reparameterization

CHELA places a short and long convolution in sequentially, reparameterizing them into a single kernel by convolving the kernels together. On the other hand, we compute convolutions in parallel and then reparameterize them to a single kernel by summing the kernels together. Further, CHELA incorporates a non-linear activation function between its short and long convolutions, which cannot be merged into one convolution. In contrast, MRConv can be properly reparameterized into convolution due to its linearity.

1.2 Weighted Combination

Prior use of structural reparameterization in 2D vision tasks has simply summed the kernels after normalization, however for 1D long sequence modelling prioritization of local information is an important inductive bias to prevent overfitting and we are the first to propose learning the linear combination of kernels via gradient descent, the importance of which we highlight in Figure 3.

1.3 Multi-resolution Fourier parameterization

We are the first to consider using a multi-resolution low-rank kernel parameterization in the Fourier domain for structural reparameterization. We note that our method is also different to S4 which considers global basis functions, whereas we sum kernels of increasing length but decreasing frequency.

2. Baseline comparisons

We thank the reviewer for highlighting new work that also uses structural reparameterization. We note that some suggested works were not, or only just available online before the NeurIPS deadline, including CHELA, which was uploaded to Arxiv after the NeurIPS deadline, making comparison impossible in our original manuscript. Nevertheless, we will include the discussion in our camera-ready version. Further, the motivation of the ImageNet experiments is to show that long 1D convolutions can be a fast and effective alternative to 2D convolutions. We feel this message would be lost if we were to start comparing against new vision models which also make changes to the backbone ConvNeXt architecture and not just the convolution. For the final version, we will include these baseline comparisons to better represent the current state-of-the-art in ImageNet classification. We will also include a detailed discussion and comparison with CHELA, which wasn't possible to provide in our original submission.

3. Convergence Plots

Following the reviewers' suggestions, we have provided convergence plots in our one-page attachment, which highlight the improvements in training stability and convergence of MRConv. In particular, we would like to thank the reviewer for this suggestion as the plots significantly improve the clarity of our ablations, highlighting MRConv's ability to avoid overfitting and strong generalisation and we will make sure to include them in the camera-ready version of our paper.

4. Kernel Selection.

In Section 5.1, we conducted an ablation study to evaluate each kernel parameterization on different LRA tasks (refer to Table 1). Our findings indicate that the performance of kernel parameterizations varies depending on the data modality. For instance, we observed that "Dilated kernels perform exceptionally well on the Image task" (Line 203), while "on information-dense tasks such as ListOps, Fourier kernels perform better," as we hypothesize that "the sparse dilated pattern of dilated kernels is prone to skipping important tokens" (Line 204). These results suggest that the performance of kernel parameterizations is influenced by the smoothness and modality of the training data, indicating that there is no one-size-fits-all solution. This observation is consistent with previous results in [1] which show that different basis functions are optimal for different LRA tasks. When faced with uncertainty, we note that 'Fourier kernels perform the best on average' (Line 206) and recommend using them as a strong starting baseline. In our revised paper, we plan to include a detailed discussion on kernel selection in different practical scenarios. We believe kernel selection is a promising future research direction that can further improve our framework and appreciate the reviewer for this suggestion!

5. Training Tricks

We are happy the reviewer raised this question as the beauty of our method is in its simplicity in training. There are no specific tricks required to train MRConv. Using different learning rates in long sequence modelling is a common practice, widely employed in advanced architecture papers such as S4, S4D, S5, LongConv, and MEGA. Furthermore, compared to these architectures, we found that the beauty of MRConv lies in its ease of use; it is less sensitive to hyperparameter tuning and does not require special initialization such as HiPPO as used by S4.

6. Conflicts with BatchNorm and LayerNorm

We find this not to be an issue. We want to highlight that although we use BatchNorm inside MRConv, the MRConv block can be directly plugged into existing architectures that use LayerNorm. For example, in our long-arena experiment in Table 1, the backbone architecture contains LayerNorms, and using MRConv still achieves the best performance, which demonstrates that MRConv can be easily integrated. We will further clarify this point in the camera-ready version.

[1] Gu, Albert, et al. "How to train your hippo: State space models with generalized orthogonal basis projections." 2022.