RotRNN: Modelling Long Sequences with Rotations

## Abstract

Abstract Linear recurrent neural networks, such as State Space Models (SSMs) and Linear Recurrent Units (LRUs), have recently shown state-of-the-art performance on long sequence modelling benchmarks. Despite their success, their empirical performance is not well understood and they come with a number of drawbacks, most notably their complex initialisation and normalisation schemes. In this work, we address some of these issues by proposing RotRNN – a linear recurrent model which utilises the convenient properties of rotation matrices. We show that RotRNN provides a simple and efficient model with a robust normalisation procedure,
and a practical implementation that remains faithful to its theoretical derivation. RotRNN also achieves competitive performance to state-of-the-art linear recurrent models on several long sequence modelling datasets.

## 1 Introduction

Long sequence modelling is a notoriously difficult domain in machine learning due to the need to capture long-range dependencies between input data.
Typical sequence models, such as Transformers (Vaswani et al., ) and Recurrent Neural Networks (RNNs) (Rumelhart et al., ; Hochreiter & Schmidhuber, ; Cho et al., ; Koutnik et al., ), fail to perform well on these tasks. In the case of Transformers this is due to poor inductive biases and quadratic scaling of computational complexity with sequence length,
and in the case of non-linear RNNs it is caused by vanishing and exploding gradients.
Recently, State Space Models (SSMs) (Gu et al., ; Smith et al., ; Gupta et al., ) have emerged as the state-of-the-art framework for learning on long-sequences of data.
The S4 model (Gu et al., ), inspired by linear time invariant dynamical systems, utilises a linear recurrent layer with HiPPO initialisation (Gu et al., ) to solve the vanishing and exploding gradient problem of classical RNNs.
Moreover, the computational complexity of S4 scales linearly in time with sequence length, and thus circumvents the quadratic computational scaling of Transformers.
Interestingly, the linear recurrence of S4 hidden state can be viewed as both a linear RNN for fast inference and as a Convolutional Neural Network (CNN) for efficient parallel training.

Despite the mathematical elegance of the S4 derivation, the question of whether such careful initialisation is required remains open.
Indeed, several subsequent works suggested that the specific initialisation and discretisation methods that theoretically motivated S4 may not be necessary for highly performant SSMs (Gupta et al., , ; Gu et al., ; Smith et al., ; Orvieto et al., ).
These findings led to the development of the Linear Recurrent Unit (LRU) (Orvieto et al., ), which showed that competitive empirical performance on long sequence modelling tasks can be achieved by making some small modifications to a standard linear RNN, without using the theoretical insights from SSMs.
While the LRU is conceptually simpler than prior works, the theoretical motivation does not necessarily reflect the practical implementation of the algorithm, leading to more unanswered questions as to why SSMs and the LRU are stable and performative on long sequence modelling tasks.

The LRU and other linear recurrent layers have been used as basic building blocks for more complex sequence modelling architectures (Gu & Dao, ; De et al., ).
Motivated by the wide adoption of such models (Zhu et al., ; Ma et al., ; Xing et al., ; Patro & Agneeswaran, ), we extend the body of work on linear RNNs by proposing a novel recurrent block, deriving a conceptually simple but mathematically principled way of performing linear recurrence by using rotation matrices. By parameterising the recurrent state matrix as a rotation, we are able to provide more stable normalisation than prior works, and allow for a robust implementation that faithfully reflects its theoretical motivation.
Importantly, our model remains consistent with the theory throughout training, and is not purely used to find a good initialisation of the recurrent matrix (Gu et al., ; Gupta et al., ; Smith et al., ).
Moreover, we derive a mathematical equivalence between a special case of the LRU and our model, in the hope that it will help shed light on some of the LRU’s internal mechanics.
We summarise our main contributions as follows:

- •
We propose a novel linear RNN layer where the recurrent state matrix $A$ is parameterised as a rotation, with the resulting algorithm faithfully reflecting the theoretical motivation throughout training.
- •
We present a method for computing efficient matrix powers of parametric rotations to enable fast linear recurrence with rotation matrices.
- •
We use this new formulation to derive a principled normalisation procedure which retains a constant expected hidden state magnitude that holds throughout training.
- •
We show competitive performance with the state-of-the-art on long sequence benchmarks, and show that the improved normalisation of our model holds on practical tasks.

## 2 Background

### 2.1 State Space Models

SSMs (Gu et al., ; Smith et al., ; Gupta et al., ) are derived from time-invariant continuous-time linear ordinary differential equations (ODEs), of the form

$$ $\displaystyle\dot{x}(t)$ $\displaystyle=A^{\prime}x(t)+B^{\prime}u(t)$ $\displaystyle y(t)$ $\displaystyle=Cx(t)+Du(t)$ $$

where $B^{\prime}\in\mathbb{R}^{{\mathcal{D}_{x}}\times{\mathcal{D}_{u}}}$ is the input matrix, $A^{\prime}\in\mathbb{R}^{{\mathcal{D}_{x}}\times{\mathcal{D}_{x}}}$ is the state matrix, $C\in\mathbb{R}^{{\mathcal{D}_{y}}\times{\mathcal{D}_{x}}}$ and $D\in\mathbb{R}^{{\mathcal{D}_{y}}\times{\mathcal{D}_{u}}}$ are the output matrices and $u(t)\in\mathbb{R}^{\mathcal{D}_{u}}$ is the continuous-time input.

Under a constant sampling rate with a given stepsize $\Delta>0$, such systems can be discretised using Zero-Order Hold (ZOH) or Bilinear discritisation. Under the ZOH method, the resulting discrete system can be expressed by the following recursion:

$$ $\displaystyle\begin{aligned} x_{t}&=Ax_{t-1}+Bu_{t}\\ y_{t}&=Cx_{t}+Du_{t}\end{aligned}$ (1) $$

where $u_{t}$ are the sampled input signals and $A=\exp(\Delta A^{\prime})$ and $B=(A-I)A^{\prime-1}B^{\prime}$ are discretised versions of the state and input matrices, respectively.
Importantly, this recurrence relation can also be unrolled and written as a convolution over the inputs,

$$ $\displaystyle\begin{aligned} x_{t}&=\sum_{k=1}^{t}A^{t-k}Bu_{k}.\end{aligned}$ (2) $$

This duality of recurrence and convolution allows for efficient parallel computation of sequence outputs during training, and fast state updating during inference. Equation 1 is the foundation of the SSM layer in S4 (Gu et al., ) and its variants (Gupta et al., ; Smith et al., ; Gu & Dao, ).
The matrix $A$ is initialised using HiPPO theory (Gu et al., ), whose derivation follows from the theory of optimal polynomial projections.

### 2.2 Linear Recurrent Units

Instead of discretising a continuous-time ODE, the LRU (Orvieto et al., ) achieves competetive empirical performance with clever parameterisation and normalisation of linear RNNs.
The derivation of the LRU is motivated by the observation that the recurrent matrix $A\in\mathbb{R}^{{\mathcal{D}_{x}}\times{\mathcal{D}_{x}}}$ can be written (up to arbitrarily small perturbation of the entries (Axler, )) as

$$ $A=P\Lambda P^{-1}$ (3) $$

where $\Lambda=\mathrm{diag}(\lambda_{1},\dots,\lambda_{\mathcal{D}_{x}})\in\mathbb{C
}^{{\mathcal{D}_{x}}\times{\mathcal{D}_{x}}}$ is the diagonal matrix of eigenvalues and $P\in\mathbb{C}^{{\mathcal{D}_{x}}\times{\mathcal{D}_{x}}}$ is a complex-valued invertible matrix of eigenvectors.
This diagonalised parameterisation is necessary to allow for fast computation of matrix powers, which is required in linear recurrent models (see Equation 2).
Premultiplying both sides of Equation 2 by $P^{-1}$, and plugging in Equation 3, we obtain

$$ $\displaystyle\begin{aligned} \tilde{x}_{t}&=\sum_{k=1}^{t}\Lambda^{t-k}\tilde{ B}u_{k}\\ y_{t}&=\tilde{C}\tilde{x}_{t}+Du_{t}\end{aligned}$ (4) $$

where $\tilde{x}_{t}=P^{-1}x_{t}$, $\tilde{B}=P^{-1}B$, $\tilde{C}=CP$. The LRU aims to directly learn the matrices $\tilde{B}$ and $\tilde{C}$, along with the eigenvalues $\lambda_{j}=\nu_{j}e^{i\theta_{j}}$, for learnable parameters $\nu_{j},\theta_{j}\in\mathbb{R}$.

### 2.3 Drawbacks of Prior Works

These prior methods for tackling long sequence modelling with linear recurrence have several drawbacks. In the case of SSMs, a complicated theoretical derivation based on polynomial projections is required to initialise the recurrent HiPPO matrix. However, this is purely used as an initialisation procedure. The inner workings of SSM models throughout training is not well understood, and more research is needed to uncover why deviation from optimal polynomial projections of functions improves results and remains stable throughout learning.
Indeed, as shown in the LRU, it is in fact unnecessary to use such theoretical motivation to achieve strong performance on long sequence benchmarks.

What actually goes on under the hood of the LRU, though, is also not entirely clear. The motivation of the LRU stems from constraining classical linear RNNs, but this is not fully reflected in the final proposed algorithm.
Firstly, eigenvalues of the real matrix $A$ come in conjugate pairs, but this is not enforced in the LRU (as it is in, for example, S5 (Smith et al., )).
Moreover, there is no constraint ensuring that $y_{t}=\tilde{C}\tilde{x}_{t}=CPP^{-1}x_{t}=Cx_{t}$ is real-valued – i.e. that the $P$ and $P^{-1}$ components of the learned $\tilde{C}$ and $\tilde{x}_{t}$ are consistent. Instead, the authors simply take the real part of the resulting complex $y_{t}$.
Additionally, the LRU is normalised (at initialisation) by ensuring expected convergence in the limit of infinite sequence length (see 4.1), but in practice a learnt normaliser is used, and does not necessarily result in desirable or consistent hidden state magnitudes (Figure 3).

In this work, we aim to overcome this mis-match between theoretical motivation and practical implementation by proposing a novel linear recurrent model using rotation matrices. Our algorithm is conceptually simple to understand, efficient to compute, robust to exploding hidden state norms, and, importantly, faithfully reflects the mathematical principles that underpin its motivation.

## 3 RotRNN

Figure: Figure 1: Full neural network architecture of the RotRNN. Here $T$ denotes the length of the input sequence, and ${\mathcal{D}_{u}}$ denotes the number of channels in the input data.
Refer to caption: x1.png

The key component of our model, which we call the Rotational Recurrent Neural Network (RotRNN), is the parameterisation of the recurrent state matrix $A$ as a rotation matrix.
The reason for this choice is three-fold:

- i)
Rotation matrices can be generated smoothly from any real-valued matrix, making them robust to initialisation and easy to constrain during training (Section 3.1).
- ii)
Rotations can be easily decomposed for fast computation of matrix powers, which is needed in linear RNNs (Section 3.2).
- iii)
The orthogonality of rotation matrices, and the fact that their eigenvalues lie on the unit circle, allows us to derive a simple normalisation scheme that retains a constant expected hidden state norm throughout training (Section 3.3).

### 3.1 Parameterising Rotation Matrices

We first consider the problem of parameterising $A$ as a rotation matrix in the linear RNN formulation.
The group comprising all rotation matrices in $\mathbb{R}^{N\times N}$ is known as the special orthogonal group, $SO(N)$, defined as follows:

$$ $\displaystyle SO(N)=\{Q\;|\;Q\in\mathbb{R}^{N\times N},Q^{\top}Q=QQ^{\top}=I, \det(Q)=1\}.$ (5) $$

To ensure that a learnable matrix $A$ remains in $SO(N)$ throughout training, instead of learning a constrained $A$ directly we can learn a general weight matrix $M\in\mathbb{R}^{N\times N}$ and smoothly map $M$ onto $SO(N)$. To do this, we make use of the following lemma:

###### Lemma 1 .

Let $M\in\mathbb{R}^{N\times N}$, let $S=M-M^{\top}$, and define $\exp(S):=\sum_{k=0}^{\infty}\frac{1}{k!}S^{k}$ as the matrix exponential. Then
$A=\exp{(S)}\in SO(N)$.

###### Proof.

See App. A.1.
∎

The matrix exponential map is surjective from skew-symmetric matrices onto $SO(N)$ (Rohan, ), so this parameterisation is sufficiently general for learning arbitrary rotation matrices.

###### Lemma 1 .

###### Proof.

### 3.2 Efficient Rotational Recurrence

Unfortunately, computing the convolutional form of linear recurrent layers (Equation 2) during training involves taking matrix powers of $A$, which is generally slow for high-dimensional, dense matrices.
To make this computation more efficient, we utilise the structure of rotation matrices, using the following result to decompose the dense rotation matrix into block-diagonal form.

###### Lemma 2 .

Let $P\in O(N)$ be an orthogonal matrix and let $\Theta\in SO(N)$ be a block-diagonal rotation matrix. Then $A=P\Theta P^{\top}\in SO(N)$. Moreover, any rotation matrix can be written in this form (Gallier & Xu, ).

###### Proof.

See App. A.2.
∎

The matrix $\Theta$ has $N/2$ blocks of the form
$\begin{pmatrix}\cos\theta_{i}&-\sin\theta_{i}\\
\sin\theta_{i}&\cos\theta_{i}\end{pmatrix}$
along the diagonal if $N$ is even, and $\frac{N-1}{2}$ blocks if $N$ is odd with the remaining value on the diagonal being 1, where $\theta_{i}\in[0,2\pi]$, $i=1,\dots,\lfloor\frac{N}{2}\rfloor$, are axis-aligned rotation angles in the space projected onto by $P$.
When computing matrix powers, the dense orthogonal matrices $P$ and $P^{\top}$ cancel out leaving $A^{k}=P\Theta^{k}P^{\top}$, where the blocks of $\Theta^{k}$ are of the form
$\begin{pmatrix}\cos k\theta_{i}&-\sin k\theta_{i}\\
\sin k\theta_{i}&\cos k\theta_{i}\end{pmatrix}$.
Therefore, by learning an orthogonal matrix $P$ and set of rotation angles $\bm{\theta}=\{\theta_{1},\dots,\theta_{\lfloor\frac{N}{2}\rfloor}\}$ directly, we can easily generate rotation matrices that are amenable to computing fast matrix powers.

It is important to note that, unlike $SO(N)$, there is no smooth surjective map from real square matrices onto $O(N)$,
the General Orthogonal group:

$$ $O(N)=\{Q\;|\;Q\in\mathbb{R}^{N\times N},Q^{\top}Q=QQ^{\top}=I,\det(Q)=\pm 1\}.$ $$

It is therefore hard in practice to parameterise $P$ such that the space of learnable $P$ covers the entire group of orthogonal matrices. Instead, we learn a general weight matrix $M\in\mathbb{R}^{N\times N}$, and use Lemma 1 to obtain $P=\exp(M-M^{\top})\in SO(N)\subset O(N)$. While this means that $A=P\Theta P^{\top}$ may not be surjective onto $SO(N)$, we find it is sufficiently general to achieve good results in practice (see Section 5).

Figure: Figure 2: A visualisation of the mulit-headed RotRNN layer outlined in Section 3.4. The ${\mathcal{D}_{u}}$-dimensional input sequence $u_{t}$, $t=1,\dots,T$, is projected onto each of the $H$ heads of dimension ${\mathcal{D}_{h}}$ by the $B^{(h)}$ matrices. Each head then independently performs a linear recurrence with different rotations and decay scales. The outputs of each head are concatenated and mixed linearly to form the final ${\mathcal{D}_{u}}$-dimensional output $y_{t}$.
Refer to caption: x2.png

###### Lemma 2 .

###### Proof.

### 3.3 Normalisation

Now that we have a way to parameterise our recurrent state matrix for efficient recurrence, we must turn to the problem of normalising the recurrent state. This is a key ingredient of long-range recurrent networks, as it ensures the hidden state does not vanish or explode across long sequences. In prior works, this is either done implicitly by discretisation, as is the case in S4 (Gu et al., ), or explicitly with a normalisation constant, as in the LRU (Orvieto et al., ).
In this work, we take an explicit approach to normalisation, leveraging the properties of the rotation matrix $A$ to derive a normalisation constant that retains a constant expected norm of the recurrent state at all times throughout training.

We define the hidden state recurrence of the RotRNN as

$$ $x_{t}=\alpha(\gamma Ax_{t-1}+Bu_{t})$ (6) $$

where $\alpha\in\mathbb{R}$ is a normalisation constant and $\gamma\in(0,1)$ is a learnable scalar decay factor which controls the trade-off in importance between recent and distant-past input values.

###### Lemma 3 .

Following Orvieto et al. (), let the inputs $u_{t}$ be sampled i.i.d., with mean 0 and variance I. Then for any constant $c$, if $\mathbb{E}\left[{||x_{1}||^{2}}\right]=c$ and $\alpha=\frac{1}{\sqrt{c\gamma^{2}+\mathrm{Tr}\left[{B^{\top}B}\right]}}$ we have that $\mathbb{E}\left[{||x_{t}||^{2}}\right]=c$ for all timesteps $t$.

###### Proof.

We will prove this by induction. Under the assumption $\mathbb{E}\left[{||x_{1}||^{2}}\right]=c$,
we only need to prove that $\mathbb{E}\left[{||x_{t-1}||^{2}}\right]=c\implies\mathbb{E}\left[{||x_{t}||^{
2}}\right]=c$ if $\alpha$ is as stated above.
Taking the expected square norm of Equation 6, we have

$$ $\displaystyle\mathbb{E}\left[{||x_{t}||^{2}}\right]$ $\displaystyle=\alpha^{2}\left({\gamma^{2}\mathbb{E}\left[{||x_{t-1}||^{2}} \right]+\mathbb{E}\left[{u_{t}^{\top}B^{\top}Bu_{t}}\right]+2\gamma\mathbb{E} \left[{x_{t-1}^{\top}A^{\top}Bu_{t}}\right]}\right)$ (7) $\displaystyle=\alpha^{2}\left({\gamma^{2}c+\mathrm{Tr}\left[{B^{\top}B\, \mathbb{E}\left[{u_{t}u_{t}^{\top}}\right]}\right]}\right)$ (8) $\displaystyle=\alpha^{2}\left({\gamma^{2}c+\mathrm{Tr}\left[{B^{\top}B}\right] }\right)$ (9) $$

Where in the first line we used the orthogonal property of the rotation matrix $AA^{\top}=A^{\top}A=I$, and in the second line we used the induction assumption that $\mathbb{E}\left[{||x_{t-1}||^{2}}\right]=c$ and that for i.i.d inputs $x_{t-1}$ and $u_{t}$ are uncorrelated. Finally, setting $\alpha=\frac{1}{\sqrt{c\gamma^{2}+\mathrm{Tr}\left[{B^{\top}B}\right]}}$ gives $\mathbb{E}\left[{||x_{t}||^{2}}\right]=c$ as required.
∎

In practice, however, we find that this naïve method of normalisation is not entirely satisfactory. Unrolling Equation 6 into its convolutional form
we obtain

$$ $x_{t}=\sum_{k=1}^{t}\alpha^{t+1-k}\gamma^{t-k}A^{t-k}Bu_{k}$ (10) $$

where we can see that the normalisation constant $\alpha$ is raised to the power $t+1-k$. When $\alpha<1$ we therefore observe that the weighting of early inputs in the sequence goes to zero exponentially, and the model quickly forgets all but the very recent past. Since we desire that the recurrent decay is controlled only by $\gamma$, we instead enforce $\alpha=1$, shifting all normalisation into the matrix $B$. This requires that $\mathrm{Tr}\left[{B^{\top}B}\right]=1-c\gamma^{2}$, which can be achieved by simply re-scaling $B$ with the coefficient

$$ $\xi:=\sqrt{\frac{1-c\gamma^{2}}{\mathrm{Tr}\left[{B^{\top}B}\right]}}.$ (11) $$

Our final expression for the recurrent and convolutional forms of the RotRNN hidden state is thus

$$ $x_{t}=\gamma Ax_{t-1}+\xi Bu_{t}\;\;\;\Leftrightarrow\;\;\;x_{t}=\xi\sum_{k=1} ^{t}\gamma^{t-k}A^{t-k}Bu_{k}$ (12) $$

which avoids the problem of unwanted exponential decay. In practice we find that setting $c=1$ is sufficient to achieve stable and robust normalisation, even in deep, multi-layer networks (Figure 3).

###### Lemma 3 .

###### Proof.

### 3.4 Multi-Head Decay

The price of having a constant expected hidden state norm in our derivation is that the decay factor $\gamma$ must be scalar.
We find, however, that this does not generalise well to problems that require retaining information from horizons at different scales.
We address this by running $H$ independent low-dimensional RotRNN heads in parallel (see Figure 2), each with a unique set of $A^{(h)}\in\mathbb{R}^{{\mathcal{D}_{h}}\times{\mathcal{D}_{h}}},B^{(h)}\in
\mathbb{R}^{{\mathcal{D}_{h}}\times{\mathcal{D}_{u}}},\gamma^{(h)}\in(0,1)$ parameters, where we set ${\mathcal{D}_{h}}=\frac{{\mathcal{D}_{x}}}{H}$.
The output projection,

$$ $y_{t}=Cx_{t}^{(1:H)}+Du_{t},$ (13) $$

where $C\in\mathbb{R}^{{\mathcal{D}_{u}}\times{\mathcal{D}_{x}}},D\in\mathbb{R}^{{
\mathcal{D}_{u}}\times{\mathcal{D}_{u}}}$, and $x_{t}^{(1:H)}$ is the concatenation of the $t^{\text{th}}$ hidden state from each head, can be viewed as a linear mixing layer. This enables the model to share information from the different rotation phase and decay horizon recurrences from each head, which is critical in tasks which require learning both long and short range dependencies between inputs. We note that, although we use ${\mathcal{D}_{h}}=\frac{{\mathcal{D}_{x}}}{H}$ in our experiments and for ease of mathematic notation, this set-up is easily scalable to any desired head dimension ${\mathcal{D}_{h}}\geq 2$.

## 4 Analysis of RotRNN and Prior Work

### 4.1 Linear Recurrent Units

The RotRNN algorithm proposed in this paper is inspired in part by the LRU (Orvieto et al., ).
As well as sharing superficial similarities in the structure of the recurrent layer, more formal comparisons can be drawn between the two architectures. In this section, we derive a mathematical equivalence between a special case of the LRU and the RotRNN, and compare the normalisation procedures of the two models.

Figure: (a) Mean $||x_{t}||_{2}$ across different recurrent layers during training in an 8-layer model.
Refer to caption: x3.png

#### Multihead RotRNN as a special case of the LRU

In practice, ignoring skip connections, the LRU recurrent layer has 3 parameter matrices: $\Lambda$, a diagonal matrix of complex eigenvalues; $\tilde{B}$, a dense, complex input matrix; $\tilde{C}$, a dense, complex linear output projection. Consider the case where the learned eigenvalues of $A$ come in complex-conjugate pairs. In this case, the matrix $\Lambda$ can be written as a block diagonal matrix of $\begin{pmatrix}\nu_{j}\cos\theta_{j}&-\nu_{j}\sin\theta_{j}\\
\nu_{j}\sin\theta_{j}&\nu_{j}\cos\theta_{j}\end{pmatrix}$, with $\tilde{B}$ and $\tilde{C}$ real matrices (see App. E of Orvieto et al. () for details). If one assumes that $\tilde{B}=P^{\top}B$ and $\tilde{C}=CP$ for some block-diagonal orthogonal matrix $P$, then, up to normalisation, this is algebraically equivalent to the multi-head RotRNN with $H=\frac{{\mathcal{D}_{x}}}{2}$ heads and the dimension of each head is ${\mathcal{D}_{h}}=2$. This is because the parallel headed structure of the RotRNN can be viewed as one big block-diagonal recurrent layer, with corresponding dimensions of $B$ that project onto each head being normalised independently, and the corresponding decay factors $\gamma^{(h)}$ modulating the eigenvalue magnitude as does $\nu_{j}$ in the LRU.

Note that, despite being algebraically possible in the LRU theoretical framework, this exact special case of the LRU is unlikely to occur naturally in the practical algorithm proposed in Orvieto et al. () (outlined in Section 2.2). This is because the model would be required to learn that $\lambda_{1:{\mathcal{D}_{x}}}$ come in conjugate pairs, and the learned $P$ components of the input and output matrices to be the diagonalising matrix of the block-diagonal $A^{(1:H)}\in\mathbb{R}^{{\mathcal{D}_{x}}\times{\mathcal{D}_{x}}}$ of the RotRNN. However, we still believe that this view of the LRU as a decayed rotation-based block can help to uncover the mechanics of its linear recurrence.

#### Normalisation differences

To compare the normalisation methods between the two algorithms, we give a brief overview of the derivation for the LRU normalisation constant found in Orvieto et al. (). Assuming white-noise input, one can calculate the expected norm of the LRU hidden state:

$$ $\displaystyle\mathbb{E}\left[{||x_{t}||^{2}}\right]$ $\displaystyle=\mathbb{E}\left[{\left(\sum_{i=1}^{t}\Lambda^{i}\tilde{B}u_{t-i} \right)^{*}\left(\sum_{j=1}^{t}\Lambda^{j}\tilde{B}u_{t-j}\right)}\right]$ $\displaystyle=\sum_{i=1}^{t}\sum_{j=1}^{t}\operatorname{Tr}\left[\mathbb{E} \left[{u_{t-i}^{*}\tilde{B}^{*}{\Lambda^{i}}^{*}\Lambda^{j}\tilde{B}u_{t-j}} \right]\right]$ $\displaystyle=\sum_{i=1}^{t}\sum_{j=1}^{t}\operatorname{Tr}[\tilde{B}\mathbb{E }\left[{u_{t-j}u_{t-i}^{*}}\right]\tilde{B}^{*}{\Lambda^{i}}^{*}\Lambda^{j}]= \sum_{i=1}^{t}\operatorname{Tr}[\tilde{B}\tilde{B}^{*}{\Lambda^{i}}^{*}\Lambda ^{i}]$ (14) $$

Since $\Lambda$ is diagonal, Equation 14 can be re-written into a summation of terms $b_{k}|\lambda_{k}|^{2}$, where $b_{k}$ is the squared norm of each row of $\tilde{B}$, and $\lambda_{k}\in\mathbb{C}$ is the $k$’th diagonal entry of $\Lambda$.
Hence the expected norm becomes:

$$ $\displaystyle\mathbb{E}\left[{||x_{t}||^{2}}\right]$ $\displaystyle=\sum_{i=1}^{t}\sum_{k=1}^{N}b_{k}|\lambda_{k}|^{2i}=\sum_{k=1}^{ N}b_{k}\sum_{i=1}^{t}|\lambda_{k}|^{2i}\xrightarrow[]{t=\infty}\sum_{k=1}^{N}b _{k}\frac{1}{1-|\lambda_{k}|^{2}}$ $$

To ensure a finite expected norm in the limit of $t\rightarrow\infty$, one can normalise the rows of $\tilde{B}$ element-wise by $\sqrt{1-|\lambda_{k}|^{2}}$.
This is similar to the RotRNN normalisation outlined in Section 3.3, as the decay parameters $\gamma^{(h)}$ in each head essentially control the eigenvalue magnitude of the $h^{\text{th}}$ recurrent state matrix.
Conversely, in RotRNN the added $\mathrm{Tr}\left[{B^{\top}B}\right]$ term applied independently across heads ensures that the expected norm of the recurrent state remains constant throughout the entire sequence, providing stronger guarantees than expected convergence at infinite sequence length.
We do, however, use the same white-noise input assumption as in (Orvieto et al., ), which we hope to be able to overcome in future work for normalisation guarantees on more general input types.

### 4.2 State Space Models

The relationship between RotRNN and other SSMs, namely S4 (Gu et al., ) and S5 (Smith et al., ), is perhaps less formally equivalent, but we can still draw comparisons between the structures of the recurrent layers. The S4 recurrence can be viewed as a stack of single-input-single-output (SISO) SSMs, whereby independent recurrent layers operate on each channel of the vector-valued input. The outputs of these independent SSMs are concatenated and passed through a “mixing layer” to combine information.
S5, on the other hand, uses a single multi-input-multi-output (MIMO) SSM as its recurrent layer, and as such does not require a separate mixing layer to share information across dimensions.
The input-output structure of RotRNN sits somewhere in-between S4 and S5. The use of multiple independent RotRNN heads outlined in Section 3 can be viewed as a stack of independent MIMO recurrent layers, in which the user may specify both the number of heads and the dimension of each head separately. Multiplication with the output matrix $C$ can be viewed as a linear mixing layer, combining information from the hidden states of each independent head. For more details on the SISO and MIMO views of S4 and S5, we direct the reader to Smith et al. ().

## 5 Experiments

We evaluate the RotRNN on several long sequence modelling datasets, comparing performance to state-of-the-art linear recurrent sequence models. RotRNN performs competitively throughout, but particularly excels on very discrete input data (such as text). We also empirically analyse our normalisation procedure compared to that of the LRU across both deep and single-layer networks.

**Table 1: Test accuracy on the LRA benchmark tasks. We follow the standard training procedures from Gu et al. (). Unless otherwise specified, we report the results of baseline methods from their respective citations.**
| Model | ListOps | Text | Retrieval | Image | Pathfinder | Path-X | Avg. |
| --- | --- | --- | --- | --- | --- | --- | --- |
| (Input Length) | (2,048) | (4,096) | (4,000) | (1,024) | (1,024) | (16,384) |  |
| S4 (Gu et al., ) | 59.6 | 86.8 | 90.9 | 91.1 | 94.2 | 96.4 | 86.5 |
| S4D (Gu et al., ) | 60.5 | 86.2 | 89.5 | 88.2 | 93.1 | 92.0 | 84.9 |
| Liquid-S4 | 62.8 | 89.0 | 91.2 | 89.5 | 94.8 | 96.7 | 87.3 |
| (Hasani et al., ) |  |  |  |  |  |  |  |
| S5 (Smith et al., ) | 62.2 | 89.3 | 91.4 | 90.1 | 95.3 | 98.6 | 87.8 |
| LRU (Axler, ) | 60.2 | 89.4 | 89.9 | 89.0 | 95.1 | 94.2 | 86.3 |
| LRU (Our Reprod.) | 57.9 | 89.4 | 89.4 | 85.2 | 90.0 | 92.8 | 84.1 |
| RotRNN (Ours) | 61.1 | 89.6 | 89.9 | 85.9 | 93.0 | 89.2 | 84.8 |

### 5.1 Long Range Arena

We evaluate the performance of RotRNN on Long Range Arena (LRA) (Tay et al., ), a set of 6 sequence modelling tasks with sequence lengths between 1K and 16K tokens and varying data modalities. Tab. 1 shows the results for RotRNN and other linear recurrent models for comparison, reporting the test accuracy at the highest validation accuracy throughout training. Overall, we find that RotRNN performs competitively with other state-of-the-art linear recurrent models.
In particular, we find that our model performs best on domains with more discrete input data, such as ListOps, Text and Retrieval, achieving the highest score of all the baselines in the IMDB classification task (Text). However, we also note that RotRNN falls short of some of the baselines on the pixel-level image tasks, such as Path-X and Cifar.

#### Hidden State Norms

We plot the mean hidden state norm of the recurrent layers of the LRU and RotRNN throughout training on the ListOps dataset in Figure 3. We find that the hidden states of the RotRNN have an almost constant magnitude throughout training, with very little variance across layer depth or random initialisations.
To contrast this, the LRU hidden state norms vary wildly across layer depth, and take far longer to converge (if ever) to a reasonably constant magnitude throughout training.
Moreover, we see that the size and variance of the norms are significantly larger that those of the RotRNN across random seeds in a single-layer network.

### 5.2 Raw Speech Classification

Since LRA (Tay et al., ) is partly a synthetic benchmark, we further evaluate RotRNN on a more natural long-sequence classification task: the Speech Commands dataset (Warden, ). This dataset contains 1s waveforms of 35 spoken English words, sampled at 16kHz. The task is to classify the word from its given sampled waveform. The results are displayed in Tab. 2. We find that RotRNN performs identically well to the LRU (Orvieto et al., ), with a similar number of parameters. It also remains very competitive with other, more theoretically complex deep state space models.

**Table 2: Test accuracy on the 35-way Speech Commands classification task (Warden, ). Unless otherwise specified, we report the results of baseline methods from their respective citations.**
| Model | Params. | 16kHz |
| --- | --- | --- |
| (Input Length) |  | (16,000) |
| S4 (Gu et al., ) | 307K | 96.1 |
| S4D (Gu et al., ) | 306K | 95.8 |
| Liquid-S4 (Hasani et al., ) | 224K | 96.8 |
| S5 (Smith et al., ) | 280K | 96.8 |
| LRU (Our Reprod.) | 283K | 95.2 |
| RotRNN (Ours) | 284K | 95.2 |

## 6 Related Work

#### Orthogonal Recurrent Networks

The use of orthogonal and rotation matrices in recurrent networks has been explored previously in non-linear RNNs. Unitary RNNs (uRNNs) (Arjovsky et al., ; Jing et al., ) prevent blow-up in long sequences by parameterising recurrent matricies with unitary matrices (an extension of orthgonality to the complex field) to ensure an eigenvalue magnitude of 1. This idea has since been applied without the need for complex numbers (Helfrich et al., ), and has inspired works replacing recurrent operators in LSTMs with rotations (Dangovski et al., ; Velici & Prügel-Bennett, ). These methods, however, still suffer from the drawbacks of classical non-linear RNNs, such as inefficient computation of recurrent states during training when compared to associative-scan based linear models.

#### Building on Linear Recurrent Models

Linear recurrent layers have recently been used as building blocks to construct more complex long sequence models. Two representative examples include Griffin (De et al., ) built on top of the LRU, and Mamba (Gu & Dao, ) built on top of S4. The key to the success of both these models is gating – the ability to construct recurrent state matrices based on the current inputs to selectively control information flow. We believe that the RotRNN could be used as a drop-in replacement for the LRU in Griffin, or be used to perform alternative gating strategies with input dependent rotations, but we leave this direction for future work.

## 7 Conclusions and Future Work

In this paper we propose RotRNN, a linear recurrent model that utilises the convenient properties of rotation matrices. We show that RotRNN performs competitively with the state-of-the-art on long-range sequence modelling benchmarks, while providing a conceptually simple and efficient algorithm. RotRNN remains faithful to its theoretical derivation throughout training, with a robust normalisation procedure that does not rely on complex initialisation.

In addition, we hope that the concrete comparisons between our model and the LRU drawn in Section 4 can shed new light on the inner workings of the LRU and similar algorithms as multi-headed rotation-based linear recurrent networks. We point future investigations towards integrating RotRNN into more complex architectures to test its downstream capacity on other domains, and implementing input dependent rotation transitions for gated rotational recurrence.

## Appendix A Proofs

In this section we provide proofs of all theorems and lemmas not proven in the main text.

### A.1 Proof of Lemma 1

To prove Lemma 1, we must first state the formal definition of $SO(N)$.

###### Definiton 4 (Special Orthogonal Group) .

The Special Orthogonal group, $SO(N)$, is defined as

$$ $SO(N)=\left\{A\in\left(\mathbb{R}^{N\times N},*\right)\;|\;A^{\top}A=AA^{\top} =I,\det(A)=1\right\}$ $$

where the group operation $*$ denotes matrix multiplication.

Hence, to prove Lemma 1, we must simply show that any matrix $M\in\mathbb{R}^{N\times N}$ under the respective transformation is both orthogonal and has determinant 1.

See 1

###### Proof.

To prove orthogonality of $A$, we will use the well-known fact that for two square matrices $P,Q\in\mathbb{R}^{N\times N}$, if $PQ=QP$ then $\exp(P)\exp(Q)=\exp(P+Q)$. Since $S$ is skew-symmetric, we have that $S^{\top}=-S$ and hence $SS^{\top}=S^{\top}S=-S^{2}$. Moreover, since the matrix exponential is defined by a power series, we have that $\exp(S)^{\top}=\exp(S^{\top})$. Putting these two together we get

$$ $AA^{\top}=\exp(S)\exp(S)^{\top}=\exp(S)\exp(S^{\top})=\exp(S+S^{\top})=\exp(S- S)=I$ (15) $$

and clearly the same is true for $A^{\top}A$. Hence, $A$ is orthogonal.

To prove that determinant is 1, we use Jacobi’s formula, which states that for any square matrix $S$, $\det(\exp(S))=\exp(\mathrm{Tr}\left[{S}\right])$. Since $S$ is skew-symmetric, we have that $\mathrm{Tr}\left[{S}\right]=0$, and hence

$$ $\det(A)=\det(\exp(S))=\exp(\mathrm{Tr}\left[{S}\right])=\exp(0)=1$ (16) $$

∎

###### Definiton 4 (Special Orthogonal Group) .

###### Proof.

### A.2 Proof of Lemma 2

See 2

###### Proof.

We provide only a proof for the first statement, as it is the only one functionally relevant for the RotRNN to be valid, but the converse statement follows trivially from the Jordan form of orthogonal matrices. For the first statement, we must again show that $A$ is orthogonal with determinant 1. The first condition is satisfied due to the orthogonality of $P$ and $\Theta$ as follows

$$ $AA^{\top}=P\Theta P^{\top}P\Theta^{\top}P^{\top}=P\Theta\Theta^{\top}P^{\top}= PP^{\top}=I$ (17) $$

and similarly for $A^{\top}A$.

The second condition is satisfied by noting that all matrices in $SO(N)$ have determinant 1, all matrices in $O(N)$ have determinant $\in\{\pm 1\}$, and $\det(P)=\frac{1}{\det(P^{\top})}$ for orthogonal $P$. Hence,

$$ $\det(A)=\det(P\Theta P^{\top})=\det(P)\det(\Theta)\det(P^{\top})=1$ (18) $$

∎

###### Proof.

## Appendix B Implementation Details

We implement the RotRNN in JAX due to its associative scan operator for fast, parallel computation of the recurrent states across long sequence. Figure 1 provides an overview of the entire RotRNN architecture. In the following subsections, we will discuss implementation details that make our code efficient and provide the hyperparameters used in our experiments. A simplified JAX implementation of RotRNN is given in App. C.

### B.1 Rotation Matrix Multiplication

We use the associative scan operation to implement the RotRNN layer with an efficient matrix multiplication algorithm, making use of the special structure of our rotation matrix. In particular, since our rotation matrix factorises into $A=P\Theta P^{\top}$, the orthogonality of $P$ means we only need to multiply by the block-diagonal matrix $\Theta$ in the associative scan. Multiplying a vector by a block diagonal matrix can be implemented efficiently, $\Theta x$ can be equivalently computed as

$$ $\displaystyle\Theta x=\begin{bmatrix}x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\\ \vdots\\ x_{{\mathcal{D}_{x}}-1}\\ x_{{\mathcal{D}_{x}}}\end{bmatrix}\odot\begin{bmatrix}\cos{\theta_{1}}\\ \cos{\theta_{1}}\\ \cos{\theta_{2}}\\ \cos{\theta_{2}}\\ \vdots\\ \cos{\theta_{{\mathcal{D}_{x}}//2}}\\ \cos{\theta_{{\mathcal{D}_{x}}//2}}\end{bmatrix}+\begin{bmatrix}-x_{2}\\ x_{1}\\ -x_{4}\\ x_{3}\\ \vdots\\ -x_{{\mathcal{D}_{x}}}\\ x_{{\mathcal{D}_{x}}-1}\end{bmatrix}\odot\begin{bmatrix}\sin{\theta_{1}}\\ \sin{\theta_{1}}\\ \sin{\theta_{2}}\\ \sin{\theta_{2}}\\ \vdots\\ \sin{\theta_{{\mathcal{D}_{x}}//2}}\\ \sin{\theta_{{\mathcal{D}_{x}}//2}}\end{bmatrix}$ (19) $$

where $\odot$ denotes element-wise multiplication.

### B.2 Hyperparameters

In our experiments we use bidirectional RotRNN layers for Pathfinder and Path-X datasets, while for the rest of the datasets we use unidirectional layers. In the bidirectional layer we reuse the parameters $P$, $\Theta$ and $B$, while the matrix $C$ is different for the forward and the backward pass. We use batch normalisation for all of our experiments, and the number of layers $L=6$ and number of heads $H=32$ were the same for all experiments. The rest of the hyperparameters are described in Tab. 3. We select initial hyperparameters from the literature surrounding Linear Recurrent Networks and State Space Models, and performed small hyperparameter sweeps for ListOps, Text, Retrieval, Image and Speech Commands, grid-searching the hyperparameter spaces for $\gamma_{\text{init}}$, $\theta_{\text{init}}$ and learning rate. We tuned the hyperparameters for Pathfinder and Path-X manually. The total number of parameters in the resulting model is very similar to the baseline models (Gu et al., ; Smith et al., ; Orvieto et al., ; Gupta et al., ; Hasani et al., ).

**Table 3: Hyperprameters used for training on LRA and Speech Commands. $D$=model dimension, $N$=recurrent layer dimension, $GLR$=global learning rate, $LR$=recurrent layer learning rate, $B$=batch size, $WD$=weight decay, $\gamma_{\text{init}}$=initialisation range for $\gamma$, $\theta_{\text{init}}$=initialisation range for $\theta$.**
| Dataset | $D$ | $N$ | $GLR$ | $LR$ | $B$ | $WD$ | Drop. | Iters. | $\gamma_{\text{init}}$ | $\theta_{\text{init}}$ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| ListOps | 128 | 256 | 1e-3 | 1e-3 | 32 | 0.05 | 0.0 | 80K | [0.5, 0.999] | $[0,\pi/100]$ |
| Text | 256 | 192 | 1e-3 | 1e-3 | 32 | 0.05 | 0.1 | 50K | [0.5, 0.8] | $[0,\pi/10]$ |
| Retrieval | 128 | 256 | 1e-4 | 1e-5 | 32 | 0.01 | 0.1 | 50K | [0.5, 0.999] | $[0,2\pi]$ |
| Image | 512 | 384 | 4.5e-3 | 1e-3 | 50 | 0.05 | 0.1 | 250K | [0.99, 0.999] | $[0,2\pi]$ |
| Pathfinder | 192 | 256 | 4.5e-3 | 1e-3 | 64 | 0.03 | 0.05 | 500K | [0.1, 0.9999] | $[0,\pi/10]$ |
| PathX | 192 | 256 | 4.5e-3 | 1e-3 | 32 | 0.03 | 0.2 | 250K | [0.999, 0.9999] | $[0,\pi/10]$ |
| Sp. Cmds. | 96 | 128 | 8e-3 | 1e-3 | 16 | 0.04 | 0.1 | 212K | [0.1, 0.9999] | $[0,\pi/10]$ |

### B.3 Parameterising and Initialising Variables

Inspired by Orvieto et al. (), to ensure $\gamma$ remains in $(0,1)$ throughout training, instead of directly learning $\gamma$ we learn parameter $\gamma_{\log}$ s.t. $\gamma=e^{-e^{\gamma_{\log}}}\in(0,1)$. We initialise $\gamma$ to be within the range $[\gamma_{\min},\gamma_{\max}]$, and $\theta$ within $[0,\theta_{\max}]$. To initialise the input and output matrices $B$ and $C$, we use the Glorot initialisation procedure (Glorot & Bengio, ). The weight matrix for the orthogonal $P$ is initialised as a random normal matrix, and we initialise $D$ as a random normal vector applied element-wise to $u_{t}$.

## Appendix C JAX RotRNN Implementation

Here we present a simplified version of the RotRNN layer written in JAX.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: The authors never concretely show (in terms of any sensible metrics, such as GPU hours etc) how efficient their model is compared to the baselines. It would be great if they could do a more thorough job at comparing their models against the baselines. The value of this question is particularly important, especially since their model performance is not significantly better than the baselines. Why wasn't their model compared rigorously in terms of efficiency?
soundness: 3
strengths: *  Good theoretical justification of parametrizing recurrent state matrix as rotation matrix:
    * Show how rotations can be easily decomposed for efficient matrix power computation
    * Show how orthogonality of rotation matrices is used for normalization, leading to almost constant hidden state norms

* Very effective normalization enabled by the orthogonality of rotation matrices (as seen in figure 3) ensuring that hidden state norms do not vanish/explode across long sequences, which is important for stable training.

* Reproducibility: detailed hyperparameters and jax code are provided for reproducibility.
summary: This paper proposes a new linear recurrent model using rotation matrices. The aim of introducing rotation matrices is to enforce the theoretical constraints of LRU that are missing in its practical implementation. Parametrizing recurrent state matrix as rotations allows the authors to present a fast method of matrix powers and also allows then to present a normalization process that helps near constant hidden state norms, both of these are essential for linear RNNs especially in long sequence domain.
weaknesses: * The proposed approach does not seem to improve the performance on the LRA benchmarks. As shown in the table 1, the proposed approach is better than baselines only on text and that too with a very small margin. While on other benchmarks and on average, it performs significantly worse (upto 10 percent points in case of Path-X).

* Also on speech commands classification task of table 2, the proposed approach is not better than any of the shown baselines.

* Although the proposed implementations using rotation matrices in this paper enables theoretical constraints of LRU, they don’t improve the performance on downstream tasks. Also, the paper does not show how efficient the proposed method is compared to the baselines in terms of compute/resource use.

---

confidence: 2
contribution: 2
initial_rating: 3
presentation: 3
questions: How well do you think this model can scale up, compared to other approaches ? 
Does it interact well as a preprocessing layer into transformer based models ? 
The block diagonal matrices look like blocks of rotations in 2D. Are these the only kinds of block rotation matrices that are possible for theta ? 
Is it possible to control the periodicity of rotations using the block diagonal 'blocks' in some way ?
soundness: 2
strengths: While I didn't look at the detailed linear algebra proofs, they seemed correct to me mathematically and made sound intuitive sense. There are also results showing that norms of the state are well preserved when the model is run, so that part of the proposal also seems to work well. The provided Jax code also makes it clear to see how the implementation matches the technical details of the paper.
summary: The paper presents a linear state space model, where the recurrent state is transformed by a rotation matrix, A, that is an exact rotation matrix, and input is transformed by an input matrix. In prior works like LRU, careful initialization is performed to ensure that the rotation matrices at the start of learning are orthogonal and that outputs of the state space model are real values . However, as training proceeds, it is possible that complex parts arrive and are ignored. In this paper, the authors propose RotRNN - a parameterization of rotation matrices that is exact (although it doesn't cover the space of all rotation matrices, if I understood correctly). To do this, the authors show that any general matrix M can be smoothly mapped to the special orthogonal group by taking the matrix exponential of M-M^t.  Now, P = exp(M-M^T) can be mapped to the special orthogonal group rotation matrix A, through a block diagonal matrix $\theta$ by A= $ P \theta P^t$.
Using this scheme orthogonal recurrent rotation matrices can be generated. 

Aside from ensuring that an orthogonal rotation matrix can be produced, the authors also ensure that the hidden state $x_t$ is well behaved an preserves a constant norm in expectation. This is performed by using a normalization constant $\alpha$ to counteract the decay factor $\gamma$ applied to the rotation of the recurrent states. In practice this is actually done by rescaling the output of the application of the input matrix to the input.


Results of using the method are shown on LRA benchmarks and on Raw Speech classification using the Speech Commands classification task.
weaknesses: While I am moved by the simplicity of their parameterization compared to prior works, I am not sure if the contribution is enough to merit a paper in ICRL with the kind of experimental exploration performed. I think a proper paper would run much further with the proposed method than the author(s) have done here. Speech commands is quite a small dataset and the results on it, and on LRA shed little light into the details of their method. And the results on these datasets are not necessarily better than prior methods. So the selling point of the method from a standpoint of improved results over LRU is not clear. Furthermore, other than showing the norms of the states are well behaved, the paper does not offer more technical insight either, for others to build upon. Without that, this is more of an exposition of a mathematical trick rather than a full contribution.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: Given that the real-part operation at the output of LRU implicitly pairs each eigenvalue with its complex conjugate, what are the remaining important differences between the proposed algorithm and LRU?

Which of the performance differences shown are statistically significant?
soundness: 3
strengths: The factorization of the linear recurrence matrix into cosine and sine rotations is elegant, and was a pleasure to read.
summary: State-based models have reduced the long-path problem of traditional recurrent models, but require complicated initialization procedures in order to avoid vanishing/exploding gradients.  This paper demonstrates a new linear recurrent unit in which the recurrence is constrained to be a rotation, scaled by a head-wise decay constant.  The head-wise decay constant is matched to the amplitude of the input coefficients, in order to guarantee that the magnitude of the state vector remains constant over time, avoiding the vanishing/exploding gradient problem without complicated initialization procedures.
weaknesses: The key weakness of this paper is a minor oversight in the analysis of LRU, which calls into question the value of this paper's contribution.

The proposed algorithm is very similar to LRU, except that it forces the eigenvalues of the recurrence matrix to come in complex conjugate pairs.  The manuscript notes this as a weakness of LRU: that LRU does not require the eigenvalues to come in complex conjugate pairs, and instead, LRU simply takes the real part of the output of the linear layer.   It seems that the authors of this paper do not realize that taking the real part of the output of the network solves the problem of arranging eigenvalues into complex conjugate pairs, because the real part of any complex number is the average of the complex number and its complex conjugate: Re(z) = (z+z*)/2.  Thus, if z(t)=P Lambda^t P^T z(0), and if z(0) is real, then Re(z) = (1/2)(P Lambda^t P^T + P* Lambda*^t P*^T) z(0).  By taking the real part of the output, LRU is pairing each explicit eigenvalue with an implicit eigenvalue equal to the complex conjugate of the explicit eigenvalue, thus effectively doubling the dimension of the recurrent layer, at no extra computational cost. 

Since LRU already has each eigenvalue paired with an implicit conjugate eigenvalue, the only remaining difference I can see between the proposed algorithm and LRU is the proposed input normalization, which guarantees that the recurrent state vector maintains constant norm.  In theory, this seems like a useful contribution, since it explicitly avoids gradient vanishing/explosion.  In practice, it's not clear that LRU suffers from problems of gradient vanishing or explosion.  In the example shown, the norm of LRU gets large, but it never seems to overflow.  The proposed algorithm has better performance than LRU on a toy example, but it is not clear that the difference is statistically significant.

---

confidence: 5
contribution: 1
initial_rating: 5
presentation: 4
questions: What does $A^{t-k}$ mean in Equation 2?
soundness: 3
strengths: Rigorous mathematical background: The math backgrounds behind the rotation matrix-based parameterization and explicit normalization method are proved with easy-to-read derivations. In addition, those backgrounds lead the simple implementation of RotRNN. 

In-depth comparison between former architectures: The theoretic comparisons between RotRNN and (LRU/SSM) are helpful to posit RotRNN within this field.

Strong, latest baselines: This paper compares RotRNN with latest and state-of-the-art baselines (such as S5 and Liquid-S4) in long-range sequence modeling benchmarks.
summary: This paper proposes a new class of linear recurrent unit (LRU) which is uprising efficient state-of-the-art model class for long-range sequence modeling. The proposed model, RotRNN, utilizes rotation matrix-based parameterization for state transformation and the explicit normalization method. Based on strong mathematical backgrounds, RotRNN could be simply implemented and strictly guarantees preservation of hidden state magnitude across time-steps. This paper compares RotRNN with former LRU and state space models (SSMs) in theory and experiments to give in-depth understanding for readers.
weaknesses: Majors:
- Limitation of rotation matrix parameterization: I think there would be drawback with constraining state transformation matrix to be rotation matrix, which might limit expression power of the model. 
- Potential drawback of explicit normalization method: It is unclear that whether the explicit normalization method is beneficial for performance. I understand that this method constrains the operation to target a specific range of dependency based on the trained value of $gamma$, so it looks constraining the model’s expressivity. Although it successfully guarantees the converged norm of hidden states during training, its performance-wise effect is not demonstrated in results. An ablation study would be helpful to see its benefit.
- Overall, it is questionable how RotRNN could be advantageous in practice. Comparison of computational efficiency (in terms of FLOPS) would be helpful to show that RotRNN is ‘efficient to compute’.

Minors:
- Weak motivations for rotation matrix parameterization: The three motivations written at the beginning of section 3 aim to simple implementation thanks to the rotation matrix parameterization. However, there is no motivation related to hidden state processing despite of rotation matrix’s unique characteristic (such as regularity). And, it is not clear why real-valued matrix can make it robust to initialization? 
- Arguable interpretations of experiment results: The sentence “we find that our model performs best on domains with more discrete input data, such as ListOps, Text and Retrieval, achieving the highest score of all the baselines” seems not clear from the result table. Except ‘Text’ task, Liquid-S4 and S5 achieved the highest scores in ListOps and Retrieval tasks, respectively.
- Confronting claims: This paper argues the unnecessity of SSM model’s theory-based initialization method (HiPPO) in practice (Section 2.3). However, this paper aims to build RotRNN on rigorous theoretic backgrounds. I think those claims are confronting with each other.