We sincerely thank the reviewer for recognizing the novelty of our framework, its potential to motivate performant sequence mixers, and superior empirical performance enjoyed by Hydra.

The reviewer's feedback highlights the following key concerns:
Q1. Ablating away the shift and the diagonal operations to understand Hydra's performance
Q2. Do separate parameters conflict with the motivations of the matrix mixer framework?
Q3-1. Clarifications on the definitions of Quasiseparable, and Structured Matrices and Data Dependence, along with further writing style comments.
Q3-2. Writing concerns.

A1) We thank the reviewer for this valuable suggestion; the ablation shows that the GLUE scores with only shift or diagonal operations matches the Add variant ($\approx 80.6$). It is only when both operations are used together do we see an improvement ($81.7$). This validates our framework, which explains this ablation by noting that a Quasiseparable (QS) matrix is strictly more expressive than adding two SS matrices.

A2) We refer the reviewer to the definition of QS matrices [C]: a matrix M is N-QS if its any submatrix from either the strictly upper or lower triangle (off-diagonal) has a rank of at most N. We remark that the matrix with non-symmetric upper and lower triangular forms is a general QS matrix and is consistent with the motivations of the Matrix Mixer framework.

A3-1) We refer the reviewer to [B, C] for the definition of QS matrices. Structured Matrices [A, B, C, 6, 8, 13, 16, 29] are a well-studied area of mathematics, defined as matrices that admit a subquadratic matrix multiplication algorithm. By data dependence in the "third interpretation" we mean that each parameter of a matrix is either a free parameter or projected from exactly one token. By canonical data dependence, we mean that the parameters of SAM matrices can naturally be made data-dependent using the bijective map $f_{\mathcal{E}}(\cdot)$.

We now provide a detailed response to all of reviewer's comments:

A1. Ablations to understand Hydra's performance

We thank the reviewer for suggesting an ablation study to assess the impact of shift and diagonal operations on Hydra's performance. In this study, we removed either the Diagonal or Shift operation, or both (equivalent to the Add method). Our results are tabulated below:

We observe that performance remains unchanged when only one operation is used. Only when both operations are used together do we see an improvement ($81.7$ vs $80.6$). This validates our framework, showing that a QS matrix is strictly more expressive than adding two SS matrices.

The reviewer has raised important ablations involving convolution operations and backbone architectures. While these are beyond the scope of this paper, as we focus on sequence mixers, they are valuable directions for future research. We refer the reviewer to the second global response where we clarify the focus of our paper on sequence mixers.

A2. Do separate parameters conflict the matrix mixer framework?

Yes, the reviewer is correct that the two halves of the matrix are discretized separately. This does not deviate from the motivations of our framework as the matrix with non-symmetric upper and lower triangular forms is simply a QS matrix. This follows from the rank characterization of QS matrices [C]: a matrix $M$ is $N$-QS if any submatrix from either the strictly upper or lower triangle (off-diagonal) has a rank of at most $N$. We note that this definition applies regardless of parameter sharing between the upper and lower halves, and that the parameter shared matrices referred by the reviewer are a strict subset of QS matrices.

Proposition 3.2 does not include this detail for pedagogical simplicity and it can easily be extended to QS matrices. To see this, divide the QS matrix into strict upper ($SS_u$), strict lower ($SS_l$), and diagonal ($D$) components, and then:

$QS(X) = \text{shift}(SS_l(X)) + \text{flip}(\text{shift}(SS_u(\text{flip}(X)))) + DX$

A3-2. Writing concerns

• “Common data transformations” refers to standard projects commonly used in the ML community, such as those implemented using convolutions or linear layers.
• Components in Definition 2.2 are necessary as they allow for multiple sets of parameters like B and C. As assumed, $\emptyset$ represents the empty set.
• By the definition of SAM, Linear Attention is sequence aligned as each element $(i,j)$ in the matrix $m_{ij}$ is parameterized by $Q_i$ and $K_j$.
• Quasiseparable matrix are closed under addition [B]
• Efficacy of data dependence and extendability is born out of the experience of the community and has been shown to be effective on long range tasks [6, 16]

We appreciate the reviewers constructive feedback on the writing, such as the typo in Line 237 and the ordering of the paper. We will address all the aforementioned issues in our next revision.

A4. Is Hydra hardware efficient?

We agree with the reviewer that hardware efficiency is indeed an important desideratum for designing new sequence models. However, achieving hardware efficiency involves a series of complex factors, making it challenging to directly target hardware-friendly models from the outset. Therefore, computational complexity is usually prioritized first, with subsequent efforts focused on developing efficient implementations.

Hydra leverages hardware-friendly kernels from Mamba, maintaining competitive speed with Transformers for short sequences. As sequence lengths increase, Hydra’s sub-quadratic design allows it to surpass Transformers in speed, addressing the quadratic bottleneck. The growing interest in processing long sequences [D, E, F] further underscores the importance of Hydra.

[A] Xia, Jianlin, et al. “Fast algorithms for hierarchically semiseparable matrices.” Numerical Linear Algebra with Applications, 17.6 (2010): 953-976.
[B] Boito, Paola. “Matrix Structures and Matrix Functions.” Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation. 2023.
[C] Pernet, Clément, Hippolyte Signargout, and Gilles Villard. "Exact computations with quasiseparable matrices." Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation. 2023.
[D] Bertsch, Amanda, et al. "Unlimiformer: Long-range transformers with unlimited length input." Advances in Neural Information Processing Systems 36. 2023.
[E] Ding, Jiayu, et al. "Longnet: Scaling transformers to 1,000,000,000 tokens." arXiv preprint arXiv:2307.02486. 2023.
[F] Liu, Hao, Matei Zaharia, and Pieter Abbeel. "Ring attention with blockwise transformers for near-infinite context." International Conference on Learning Representations. 2024.

We are grateful to the reviewer for their continued engagement and thoughtful questions. And we appreciate this opportunity to provide further clarification on their concerns:

1. Expressivity of the "No Shift/Add" (Figure, c) variant :

We would first like to clarify that there is no data-dependent $DX$ term in the "No Shift" variant. Intuitively, the "No Shift" variant exhibits reduced expressivity compared to general QS matrices (Figure, d) because the diagonals in $SS_l$ and $SS_u$, specifically $\overrightarrow{c}^T \overrightarrow{b} + \overleftarrow{c}^T \overleftarrow{b}$, share parameters with the non-diagonal elements. This parameter tying limits the model’s expressivity, as it cannot independently assign values to the diagonal elements.

Mathematically, observe that the "No Shift" variant satisfies the definition of an N-QS matrix [C] and therefore is a subset of the N-QS matrices (Figure, d). Furthermore, the "No Shift" variant is a strict subset of general N-QS matrices because the lack of shift forces additional constraints on the matrix class. For instance, in general QS matrices, the diagonal is freely parameterized, while in the "No Shift" variant, it is a function of non-diagonal elements, $\overrightarrow{c}, \overrightarrow{b}, \overleftarrow{c}, \overleftarrow{b}$.

Our additional ablations reported in our first response (A.1) at the reviewer's suggestion validate this increase in expressivity by demonstrating an improved performance of N-QS matrices compared to the "No Shift" and the "No Diagonal" variants, which are strict subsets of N-QS matrices.

2. Role of Convolution and Block Structure

We would like to begin by noting that a short convolution within the block is a standard element used across a vast majority of sub-quadratic models like Mamba2[6], H3[14], Mamba[16], Hyena[29]. We fully agree with the reviewer's insight that investigating the impact of block structure on the performance of the matrix mixer is important, and this is indeed being explored in parallel works like [G]. However, in our work, we focused specifically on fixing a sub-quadratic block [6] to control for the impact of the matrix mixer. We simply selected the block architecture from Mamba2 [6] as it is one of the latest iterations of sub-quadratic models. With this view, we sincerely believe that the reviewer’s suggestion of understanding the impact of these architectural choices outside of the matrix mixer would be an important follow-up work.

3. Scope of Changes

We are truly grateful for the reviewer's valuable suggestions to improve the clarity and accessibility of our work. However, we would like to emphasize that our changes primarily involve adding more precise and mathematically complete definitions, and this would not alter the core results or contributions of the paper.

[G] Yang, Songlin, et al. "Parallelizing Linear Transformers with the Delta Rule over Sequence Length." arXiv preprint arXiv:2406.06484 (2024).

We genuinely appreciate and thank the reviewer for their continued interest and detailed consideration of our work.

1. Expressivity of QS ablation matrices

We would like to clarify our previous response: we commented on the expressivity of (Figure, c) which corresponds to the "Add" ablation and not the "No-Shift" ablation. We apologize for the misunderstanding and would like to take the opportunity to clarify the expressivity of all variants of the quasiseparable ablations that the reviewer suggested.

For convenience, we reproduce the ablation table below:

Lemma: The matrix classes satisfy the following inclusions: $\text{Add} \subseteq \text{No-Shift} \subseteq \text{QS}, \quad \text{and} \quad \text{No-Diag} \subseteq \text{QS}.$

Proof:

1. $\text{Add} \subseteq \text{No-Shift}$

To see this, observe that we can characterize the set of No-Shift matrices as: $\text{No-Shift} = \\{ W + D \\: | \\: \forall W \in \text{Add}, \\: \forall D \in \text{diag}(\mathbb{R}^d)\\}.$Choosing $D$ to be the zero matrix, we have the result: $\text{No-Shift} \supseteq \\{ W + \mathbf{0} \\: | \\: \forall W \in \text{Add}\\} = \text{Add}$

2. $\text{No-Shift} \subseteq \text{QS}$

Let $\tilde{SS}_u$ and $\tilde{SS}_l$ denote the (the tilde represents "not strict") upper-triangular and lower-triangular N-Semiseparable matrices. Then, $\text{No-Shift} = \\{ M = \tilde{SS}_u + \tilde{SS}_l + D \\: | \\: \forall \tilde{SS}_u,\\: \tilde{SS}_l, \\: \forall D \in \text{diag}(\mathbb{R}^d)\\}.$ We apply the definition of N-QS matrices [C]. Without loss of generality, consider any submatrix $L$ in the strict lower triangular half of $M$. Observe that $L$ is also a submatrix of $\tilde{SS}_l$. By the definition of N-Semiseparable matrices, $\text{Rank}(L) \le \text{N}$, which implies $M \in \text{QS}$, and hence $\text{No-Shift} \subseteq \text{QS}$

We also kindly refer the reviewer to [H, §4.1.5], which discusses this result in detail.

3. $\text{No-Diag} \subseteq \text{QS}$

Let $SS_u$ and $SS_l$ denote strict upper-triangular and strict lower-triangular parts of a N-Quasiseparable matrices. Then, $\text{No-Diag} = \\{ SS_u + SS_l \\: | \\: \forall SS_u,SS_l \\},$

$\text{QS} = \\{ SS_u + SS_l + D\\: | \\: \forall SS_u,SS_l, \\: \\: \forall D \in \text{diag}(\mathbb{R^d}) \\}.$

Restricting $D$ to be the zero matrix in the definition of $\text{QS}$, we have the required result.

We now tie the expressivity of different variants with their empirical performance: higher the expressivity, higher the GLUE score. That is the performance follows the same order: $\text{QS}(81.7) > \text{No-Shift}(80.7) > \text{Add}(80.6)$, and that $\text{QS}(81.7) > \text{No-Diag}(80.7)$. This validates our premise of principally deriving QS from the Matrix Mixer framework over using its heuristical counterparts.

We again thank the reviewer for suggesting this ablation. We have now added it to our paper and incorporated our discussions on expressivity into the appendix.

[H]: Eidelman, Y., Gohberg, I., & Haimovici, I. (2013). Separable Type Representations of Matrices and Fast Algorithms: Volume 1 Basics. Completion Problems. Multiplication and Inversion Algorithms. Springer, Basel, Switzerland. Link.

Further ablations on the impact of convolution

We appreciate the reviewer's interest in understanding the impact of non-matrix mixer backbone components, such as convolution, on the model's performance. Below, we provide an ablation study to quantify the impact of removing the short convolution from the backbone. Due to the time constraints, we are currently comparing the variants on their pretraining validation accuracy and cross-entropy loss.

We make the following observations: 1) QS consistently outperforms the Add variant, both with and without convolution. 2) Adding a short convolution consistently improves the performance of both Add and QS.

This indicates that the established advantages of Quasi over heuristics like Add, Concat, and Multiply persist across changes to the underlying backbone. At the same time, we fully agree with the reviewer that further studies on backbone components are valuable and can indeed help enhance the performance of sequence mixers in general.

We sincerely thank the reviewer for the thorough evaluation and for recognizing the novel contributions of our framework. We are pleased that the reviewer appreciated the bidirectional capabilities, the valuable insights provided by the matrix mixer perspective, and the extensive experimental validation across both language and vision tasks.

We now address the reviewer’s key questions:

Scalability to larger models (~1.5B parameters)

While our experiments primarily focused on models with ~100M parameters due to resource constraints, Hydra is certainly scalable. We anticipate that Hydra will continue to demonstrate effectiveness in non-causal tasks as the model size increases.

Comparison with stacked bidirectional mamba frameworks:

We appreciate the suggestion to compare Hydra with previous stacked bidirectional Mamba frameworks (e.g., provided references). Under the matrix mixer perspective, most of these methods fall into Add, Mult, or Concat categories listed in Table 3. As demonstrated, the quasiseparable matrix mixer used in Hydra outperforms other bidirectional variants. Therefore, we confidently expect that substituting the bidirectional components of previous models with Hydra would lead to a boost in performance.

Computational resources and training time:

As similar to all other bidirectional extensions of Mamba [12, 15, 42], Hydra does introduce additional computations due to its bidirectional nature. However, unlike many of the previous extensions that utilize two completely separate unidirectional components, Hydra greatly reduces this overhead by sharing the projection layer for both forward and backward sequence processing and by batching both directions to maximize GPU utilization. This approach results in only a ~30% reduction in throughput compared to Mamba.

Performance of different matrix mixers on general tasks:

Hydra, derived from the matrix mixer framework, has demonstrated significantly stable training and enhanced performance across well-established domains such as vision and NLP. We are confident that models developed using the matrix mixer framework, when logically designed for specific domains, will continue to achieve superior performance across a diverse range of tasks.

We thank the reviewer for their insightful comments and we are glad that they found our Matrix Mixer framework informative and the Hydra model simple and effective.

The review focuses on the following concerns:
Q1. The main comparison table (Table 4) does not include any recent transformers or mamba-based models. Could authors show at least one more example application that Hydra can be useful?
Q2. Paper presentation issues
Q3. Speed comparisons between Quasiseparable and other naive approaches

We now answer these questions in detail below:

A1. Table 4 does not include recent models and the two domains chosen are limited

(Table 4) does not include any recent transformers or mamba-based models

We reiterate that the primary objective of Table 4 is to compare the core sequence mixers proposed by earlier works. Many recent works, including Caduceus [36], BiGS [42], and Vision Mamba [46], simply use the Add, Concat, or Element-wise multiplication heuristic on Mamba. These comparisons have already been included in our experiments in Table 3.

We acknowledge that integrating the Quasiseparable matrix mixer into domain-specific backbones presents excellent directions for domain-specific future work; however, these efforts are beyond the scope of this paper.

Could authors show at least one more example application that Hydra can be useful?

We chose the MLM and ImageNet-1k classification tasks since they are canonical tasks used by previous works that proposed new sequence mixers like M2[13] and Hyena[29] and their baselines are well-tuned and established. We are confident our method will also excel in other domains such as DNA modeling and graphs. We invite domain-specific research communities to explore Quasiseparable in their applications.

A2. Paper presentation issues

We appreciate the reviewer’s feedback on the structure of our paper. We would like to convey that we structured our paper this way to match the flow of our contributions:

1. Formalization of the Sequence Mixer: In Section 2.1, we formalize a sequence mixer as a generalized matrix mixer, identifying the computational bottleneck as the cost associated with the matrix class. This leads us to focus on structured matrices.
2. Optimal Structured Matrices: In Section 2.2, we define SAM matrices, characterizing structured matrices that enjoy data dependence and extendability to determine which classes would have superior empirical performance.
3. Framework Generality: In Section 2.3, we demonstrate the broad applicability of our framework by showing that more than 13 past methods, including Attention [40], Mamba [6, 16], MLP-Mixer [38], and Linear Attention [22], fall under this paradigm, indicating our framework’s generality.
4. Validation and Prescriptive Power: In Section 2.4, we validate our framework's prescriptions by identifying Cauchy, Vandermonde, and Quasiseparable matrices as Sequence Aligned Matrices (SAM) which have not been fully utilized in past works and showing that they exhibit strong empirical performance.
5. Hydra: We chose Quasiseparable matrices due to their hardware properties and connections to Mamba, scaling them up and proposing them as the next sequence mixer of choice. We show that Quasiseparable outperforms other sequence mixers on bidirectional language modeling (+0.8 over BERT) and ImageNet-1k image classification (+2.2 over ViT).

We request the reviewer to also take a look at the first global response wherein we enlist our core contributions in depth and tie them to the different sections of the paper

A3. Speed comparison between QS and naive approaches

Hydra shares the projection layers for both forward and backward passes, with the additional computation over Mamba being the backward SSD. However, the computations for forward and backward passes can be parallelized by batching, resulting in only a ~30% reduction in throughput compared to Mamba.

We thank the reviewer for recognizing the detailed categorization of prior methods using the Matrix Mixer framework and for appreciating Hydra’s simple yet effective design.

We now address the reviewer’s concerns as follows:

A1. Ablations on extendability:

The extendable property of sequence mixers is implicitly validated throughout our experimental section. Non-SAM matrix mixers, such as the Dense variant (e.g., MLP-Mixer [38]), lack extendability and require retraining from scratch when adapting to different sequence lengths. Therefore, in Table 2, we fixed the sequence length to 128 across all variants to ensure a fair comparison, thus emphasizing data dependence (DD) only. Conversely, Hydra, as a SAM matrix mixer, inherently supports both data dependence and extendability. Specifically, in Table 4, Hydra was pretrained on sequences of length 128 (C4) and then fine-tuned with sequences of length 256 (GLUE).

A2. Computational complexity of Hydra compared to Mamba:

Hydra shares the projection layers for both forward and backward passes, with the additional computation over Mamba being the backward SSD. However, the computations for forward and backward passes can be parallelized by batching, resulting in only a ~30% reduction in throughput compared to Mamba.

A3. Comparisons to Advanced Methods such as xLSTM

We thank the reviewer for pointing out xLSTM, and indeed there are many recent subquadratic models that have shown to be performant. We specifically chose to focus on Mamba as it is a recent model that introduces an interpretation of recurrent models as matrix mixers, which is the main focus of our work. Furthermore, since xLSTM is language model and does not have canonical bidriectional variants so it is not a suitable for comparison on bidirectional tasks.

A4. Analysis on Implicit Reparameterization:

We appreciate the reviewer’s observation that the same matrix class can be parameterized differently. However, this property is orthogonal to the underlying matrix class and its computational complexity. Specifically, an implicitly parameterized mixer like CKConv [35] and S4 [18] is indeed a Toeplitz matrix mixer, as indicated in Table 1. Therefore, the conclusion in Line 117 remains accurate.

A5. Clarification of the ‘Sequence Aligned’ Terminology in Table 1:

The formal definition of Sequence Aligned Matrices (SAMs) is provided in Definition 2.2. To summarize informally, SAMs ensure that the parameters for every submatrix $M[: i+1, :i+1]$ are functions only of the tokens up to index $i$.