Quantized Approximately Orthogonal Recurrent Neural Networks

## Abstract

Abstract Orthogonal recurrent neural networks (ORNNs) are an appealing option for learning tasks involving time series with long-term dependencies, thanks to their simplicity and computational stability. However, these networks often require a substantial number of parameters to perform well, which can be prohibitive in power-constrained environments, such as compact devices. One approach to address this issue is neural network quantization. The construction of such networks remains an open problem, acknowledged for its inherent instability. In this paper, we explore the quantization of the recurrent and input weight matrices in ORNNs, leading to Quantized approximately Orthogonal RNNs (QORNNs). We investigate one post-training quantization (PTQ) strategy and three quantization-aware training (QAT) algorithms that incorporate orthogonal constraints and quantized weights. Empirical results demonstrate the advantages of employing QAT over PTQ. The most efficient model achieves results similar to state-of-the-art full-precision ORNN and LSTM on a variety of standard benchmarks, even with 3-bits quantization.

## 1 Introduction

#### Motivation:

Machine learning applications frequently encompass the analysis of time series data, ranging from textual information to audio inputs. Within the realm of deep learning, various Recurrent Neural Network (RNN) architectures, including vanilla RNNs [], Long Short-Term Memory networks (LSTM) [], Gated Recurrent Units (GRUs) [],
Unitary RNNs (URNNs) [] and Orthogonal RNNs (ORNNs) []
have demonstrated notable success in addressing a diverse array of tasks associated with time series data. Additionally, when very large datasets are available, the advent of transformer architectures leveraging attention mechanisms has permitted the further improvement of the performances at the cost of larger models and increased numerical complexity [].

These models typically necessitate a substantial number of parameters for optimal performance and entail numerous matrix-vector multiplications during inference, involving matrices and vectors of considerable sizes. However, in numerous instances, there is a need for these models to operate on compact devices with constrained power resources, such as embedded systems. Moreover, these devices might face limitations in memory space for storing extensive model weights. Even in the context of non-embedded systems, constraining the power consumption of RNNs allows for the reduction of system costs and contributes to achieving a more favorable carbon footprint. Ultimately, computational speed proves to be critical for a myriad of applications.

An effective approach to address these challenges is neural network quantization []. This technique aims to reduce the number of bits required to represent the weights and/or activations of the network. On one hand, with appropriate hardware, this accelerates runtime computations, lowers power consumption, and, on the other hand, decreases the amount of space needed for parameter storage. However, depending on the neural network architecture, application, and the chosen quantization strategy, there may be performance degradation [, , , ].

Our goal is to contribute to the field of quantization of RNNs, with a particular emphasis on addressing long-term dependencies in time series.
To do so, we propose and compare
four strategies for building Orthogonal or approximately-Orthogonal Neural Networks (ORNNs) with quantized weights. We call them Quantized Orthogonal Recurrent Neural Networks (QORNNs).
We assess the methods across various bitwidths on several standard benchmarks.

#### QORNNs are a tempting solution:

Vanilla RNNs are notoriously challenging to train due to issues with vanishing and exploding gradients [].

Figure: Figure 1: Denote by $q_{k}$ the quantizer with bitwidth $k$ as defined in [Section 3.3](#S3.SS3), $\sigma_{min}(q_{k}(W))$ and $\sigma_{max}(q_{k}(W))$ the smallest and largest singular values of the matrix $q_{k}(W)$ respectively for $W\in\mathbb R^{10\times 10}$ a uniformly sampled orthogonal matrix. (Left) $\frac{\|W^{p}-(q_{k}(W))^{p}\|_{F}}{\|W^{p}\|_{F}}$ for various $k$ and powers $p$. (Right) Boxplots for $1000$ random orthogonal matrices $W$ of the ratio $\sigma_{min}(q_{k}(W))/\sigma_{max}(q_{k}(W))$ for various $k$.
Refer to caption: /html/2402.04012/assets/x1.png

LSTM [] and GRU [] are recurrent architectures that tackle vanishing gradient problems by incorporating gating mechanisms.
They have demonstrated outstanding performance in tasks such as speech recognition [] and neural machine translation []. Several variants of quantized LSTM and GRU have been studied in the literature (see [Section 2.2](#S2.SS2)).

Recently, Transformer architectures [] have shown great performance even for long sequences. However, they require large training sets and exhibit a computational complexity that increases quadratically with the length of the sequence during inference. Several contributions [, ] have demonstrated that quantization strategies are possible.

ORNN (and URNN) are known to achieve superior performance compared to LSTM in handling time series with long-term dependencies []. They explicitly address the issues of vanishing and exploding gradients by imposing orthogonality (and unitary) constraints on the recurrent weight matrix of a vanilla RNN (See [Section 2.1](#S2.SS1)). As a bonus, a standard ORNN unit contains about four times fewer parameters than an LSTM unit.

To the best of our knowledge, quantization of ORNN has not been previously investigated. These are the reasons why, in this paper, we focus on quantized ORNN (^1^11Given that ORNNs achieve comparable performance to URNN [], in the scope of lower complexity, we limit this study to ORNN).

#### QORNN are hard to train:

We emphasize that quantizing vanilla RNN and ORNN is challenging. It is identified as an open unstable problem in [, , ]. The instability can be attributed to the following phenomena:

- •
The recurrent weight matrix is applied multiple times, rendering the network’s output highly sensitive to even slight variations in the recurrent weight matrix.
- •
The quantization of an orthogonal recurrent weight matrix generally results in a matrix that is not orthogonal. This, too, can contribute to the instability of the RNN.

Let us illustrate the first point in [Figure 1](#S1.F1)-(Left):
We present in [Figure 1](#S1.F1)-(Left) the values of $\frac{\|W^{p}-q_{k}(W)^{p}\|_{F}}{\|W^{p}\|_{F}}$ for different bitwidths $k$ and
various $p-th$ power(^2^22The analysis made in this paragraph does not take into account the effect of the activation function of the RNN.) of the matrices.
Here, $\|.\|_{F}$ represents the Frobenius norm, $W\in\mathbb R^{10\times 10}$ is a random matrix sampled according to a uniform law over square orthogonal matrices of size $10\times 10$, $q_{k}$ is the quantization described in [Section 3](#S3), and $p\in\{1,10,100,200\}$. On [Figure 1](#S1.F1)-(Left), we see that $q_{k}(W)^{p}$ can be far from $W^{p}$, especially for small bitwidths $k$ and large values of $p$.
As a result of this instability, the results of the forward pass using the quantized recurrent weights are far from the results for the full-precision recurrent weights,
which may pose challenges in learning the quantized recurrent weights.

We illustrate the second point in [Figure 1](#S1.F1)-(Right): We present boxplots of the ratio $\sigma_{min}(q_{k}(W))/\sigma_{max}(q_{k}(W))$, where $\sigma_{min}(q_{k}(W))$ and $\sigma_{max}(q_{k}(W))$ are respectively the smallest and largest singular values of $q_{k}(W)$. We uniformly sample $1000$ orthogonal matrices $W$ as described above, apply the quantizer $q_{k}$ to each of them for different bitwidths $k$, and compute the ratio $\sigma_{min}(q_{k}(W))/\sigma_{max}(q_{k}(W))$. A ratio closer to $1$ indicates a higher level of orthogonality. The boxplots show that smaller bitwidths result in smaller expected ratios and more variable ratios.

As we will see, these two sources of instability make it very challenging to achieve efficient low-bit QORNNs.

#### Contribution:

This paper presents pioneering work in the exploration of the quantization of Orthogonal Recurrent Neural Networks (ORNN). Our main contributions can be summarized as follows:

- •
We investigate the factors influencing the impact of quantization on orthogonality and the behavior of ORNNs.
- •
We describe and empirically compare four different learning strategies for constructing Quantized and approximately Orthogonal Recurrent Neural Networks (QORNN). The most efficient strategy is a Quantization-Aware Training (QAT) algorithm that applies an orthogonal projection to full-precision weights first, followed by quantization, and is optimized using the Straight-Through Estimator (STE).
- •
We showcase the
viability of QORNNs by empirically establishing that a QORNN, using 5 bits only, can successfully learn long-term dependencies in benchmark tasks such as the adding task and the copy task. We achieve state-of-the-art results on the permuted pixel-by-pixel MNIST (pMNIST) task, even with 3-bit quantization.

#### Organization of the paper:

We discuss articles related to ORNNs and the quantization of vanilla RNNs in Sections [2.1](#S2.SS1) and [2.2](#S2.SS2), respectively. The notation and technical descriptions related to vanilla RNNs, orthogonality, and quantization are presented in Sections [3.1](#S3.SS1), [3.2](#S3.SS2), and [3.3](#S3.SS3), respectively. Bounds on the orthogonality discrepancy of the quantization of orthogonal matrices are provided in [Section 3.4](#S3.SS4). The four algorithms for building QORNNs are detailed in [Section 4](#S4). Finally, experiments and their results are presented in [Section 5](#S5). Additional details can be found in the appendices. The code implementing the experiments is available at ANONYMIZED.

## 2 Related works

### 2.1 URNNs and ORNNs

Learning the unitary and orthogonal recurrent weight matrix of recurrent neural networks has a rich history of study in the last decade. We describe the contributions in chronological order of publication. Unitary recurrent neural networks were introduced in []. In this article, the recurrent weight matrix is the product of parameterized unitary matrices of predefined structures. They argue empirically that URNNs are beneficial because they better capture long-term dependencies than LSTMs. Soon after, the authors of [] use the Cayley transform locally to build an iterative scheme capable of reaching all unitary matrices. In [], the authors parameterize the recurrent weight matrix as a product of Givens rotations and a diagonal matrix. By doing so, they achieve more efficient models with tunable complexity that can be trained more rapidly. In [], the authors parameterize the recurrent weight matrix as a product of Householder reflections to reduce the complexity of full-capacity models. In the same line of research, the authors of [] explore the use of product of unitary Kronecker matrices. They incorporate a soft-orthogonality penalization term to enforce the unitary constraints. The Kronecker architecture can be adjusted to reduce the complexity of the model. In [], the authors compare soft and hard-orthogonality constraints. They find that the parameter of the soft-orthogonality strategy under study can be tuned to achieve an approximately orthogonal recurrent matrix, leading to improved efficiency. In [], the authors narrow their focus to orthogonal recurrent weight matrices and parameterize the entire Stiefel manifold using the Cayley transform scaled by a diagonal and orthogonal matrix. Similar to [], the number of parameters defining the orthogonal matrix is optimal. In [], the authors parameterize orthogonal matrices using the exponential map. Finally, in [], the authors develop two Riemannian optimization strategies. The first one is based on the orthogonal projection onto the Unitary or Stiefel manifold, and the other on Riemannian geodesic shooting. The algorithms are named ProjUNN, and one of them is employed in the presented work. This choice is motivated by the experiments outlined in [].

### 2.2 Quantized RNNs

As mentioned earlier, the quantization of RNNs has been recognized as an open problem since 2016 []. In this article, the authors argue that quantizing vanilla RNNs is unstable. In this article, the authors only report experiments on exponential quantization for next character prediction tasks on Penn TreeBank and text8 datasets. The instability problem is also reported in [, ]. To the best of our knowledge, these articles are the only ones addressing the quantization of RNNs.

There are numerous studies on the quantization of LSTM, GRU, BERT, and transformers [, ]. The proposals differ in various aspects, including the quantization scheme, the optimization strategy, and the quantization of the activation function.

## 3 Preliminaries and notations

In this section, we provide the main ideas and notations used
on the RNN architecture, orthogonality, and quantization.

### 3.1 Vanilla RNNs

Vanilla RNNs define functions that take a time series as input and produce a vector (in the many-to-one case) or a time series (in the many-to-many case) as outputs.

In order to define them, we consider positive integers $n_{i}$ and $T$, and an input time series $(x_{t})_{t=1}^{T}\in(\mathbb R^{n_{i}})^{T}$ of length $T$, made of $n_{i}$-dimensional data points. Denoting the output size $n_{o}\in\mathbb N$, the output is either a vector in $\mathbb R^{n_{o}}$ or a time series in $(\mathbb R^{n_{o}})^{T}$.

The architecture of the RNN is defined by a hidden layer size $n_{h}\in\mathbb N$, an activation function $\sigma$ and an output activation function $\sigma_{o}$. The parameters defining the vanilla RNN are $(W,U,V,b_{o})$ for a recurrent weight matrix $W\in\mathbb R^{n_{h}\times n_{h}}$, an input-to-hidden matrix $U\in\mathbb R^{n_{h}\times n_{i}}$, a hidden-to-output matrix $V\in\mathbb R^{n_{o}\times n_{h}}$, and bias $b_{o}\in\mathbb R^{n_{o}}$. The hidden-state is initialized with $h_{0}=0$
and then computed using

$$ $h_{t}=\sigma\left(Wh_{t-1}+Ux_{t}\right)\in\mathbb R^{n_{h}},$ (1) $$

for $t\in\llbracket 1,T\rrbracket$.

In the many-to-one case, the output of the vanilla RNN is

$$ $\sigma_{o}(Vh_{T}+b_{o})\in\mathbb R^{n_{o}}.$ $$

In the many-to-many case, the output of the vanilla RNN is

$$ $\Bigl{(}\sigma_{o}(Vh_{t}+b_{o})\Bigr{)}_{t\in\llbracket 1,T\rrbracket}\in(\mathbb R^{n_{o}})^{T}.$ $$

In all the experiments, $\sigma$ is either the ReLU or the modReLU [] activation functions, $\sigma_{o}$ is the identity function for regression tasks and the softmax function for classification tasks.
The parameters $(W,U,V,b_{o})$ are learned and $W$ is constrained to be quantized and approximately orthogonal.
The matrix $U$ is also quantized.

### 3.2 Orthogonality

The matrix $W\in\mathbb R^{n_{h}\times n_{h}}$ is orthogonal if and only if

$$ $W^{\prime}W=WW^{\prime}=I,$ $$

where $I$ denotes the identity matrix in $\mathbb R^{n_{h}\times n_{h}}$ and $W^{\prime}$ is the transpose of $W$.
This necessitates that the columns (respectively, rows) of the matrix possess a Euclidean norm of $1$, with the additional condition that any two distinct columns (respectively, rows) exhibit a scalar product of 0 0. Among the various properties of orthogonal matrices, it is important to note that the singular values of orthogonal matrices are all equal to $1$. Denoting $\sigma_{\min}(W)$ and $\sigma_{\max}(W)$ as the smallest and largest singular values of $W$, we have $\sigma_{\min}(W)=\sigma_{\max}(W)=1$. In other words, multiplication by an orthogonal matrix preserves norms. Orthogonal matrices constitute the Stiefel manifold [] that we denote $St(n_{h})$.

The motivation for constraining the recurrent weight matrix to be orthogonal has been discussed in numerous articles. We reiterate it for completeness in [Appendix A](#A1).

As is common, we distinguish between hard orthogonality and soft orthogonality. In the models described in Section [Section 4](#S4), we utilize tools from both of these categories.

#### Soft-orthogonality

The typical strategy for soft orthogonality involves adding a regularization term to the learning objective $L$. An effective example of such a regularization term is

$$ $R(W)=\|WW^{\prime}-I\|_{F}^{2},$ (2) $$

where $\|.\|_{F}$ denotes the Frobenius norm. Depending on the value of the parameter that balances $L$ and $R$, orthogonality is enforced more or less strictly.

#### Hard-orthogonality

Hard orthogonality strategies rigorously impose $W$ to be orthogonal. We consider two such strategies. Both strategies establish a mapping from $\mathbb R^{n_{h}\times n_{h}}$ to $St(n_{h})$.

- •
projUNN: The first strategy employs the mapping $P_{\text{projUNN}}$ as defined and implemented, referred to as projUNN-D, in []. This mapping computes the image $P_{\text{projUNN}}(W)$ of matrix $W$ as the nearest orthogonal matrix in terms of the Frobenius norm. The implementation relies on a closed-form expression derived in []. In the sequel, we use $P_{\text{projUNN}}$ to implement a projected gradient descent algorithm solving a minimization problem involving an orthogonality constraint.
- •
Björck:
The second strategy apply a fixed and sufficiently large number of iterations of the gradient descent algorithm minimizing $R$ [, ] (more details in [Appendix B](#A2)). The resulting mapping from $\mathbb{R}^{n_{h}\times n_{h}}$ to the Stiefel manifold $\text{St}(n_{h})$, denoted as $P_{\text{Björck}}$, is surjective.
Therefore, minimizing $L(P_{\text{Björck}}(W))$ among unconstrained $W$ is equivalent to minimizing $L(W)$ among orthogonal $W$.
Notice that standard backpropagation permits to compute $\left.\frac{\partial L\circ P_{\text{Björck}}}{\partial W}\right|_{W}$.

### 3.3 Quantization

We consider in this paper the most common scheme of quantization: a uniform quantization with a scaling parameter [, ].
For a quantization of bitwidth $k$, where $k\geq 2$, the
set of possible values is restricted to a set of size $2^{k}$, defined for a given $\alpha>0$, as follows:

$$ $\mathcal{Q}_{k}=\frac{\alpha}{2^{k-1}}\left\llbracket-2^{k-1},2^{k-1}-1\right\rrbracket.$ $$

The set $\mathcal{Q}_{k}$ evenly distributes values between $-\alpha$ and $\alpha-\frac{\alpha}{2^{k-1}}$, with a quantization step of $\frac{\alpha}{2^{k-1}}$.

For given $k$ and $\alpha$, the quantizer $q_{k}$ maps every $W\in\mathbb R^{n_{h}\times n_{h}}$ to the nearest element in $\mathcal{Q}_{k}^{n_{h}\times n_{h}}$ based on the Frobenius norm(^3^33Note that this paper only consider weight quantization since it has the largest influence on convergence.). In other words, for every $(i,j)\in\llbracket 1,n_{h}\rrbracket^{2}$, the entry $(i,j)$ of the matrix $q_{k}(W)$, denoted $\bigl{(}q_{k}(W)\bigr{)}_{i,j}$, is the nearest element in $\mathcal{Q}_{k}$ to $W_{i,j}$.

All considered quantizers take the value $\alpha=\|W\|_{\max}$, where
$\|W\|_{\max}=\max_{i,j}|W_{ij}|$. For ease of notation, we do not explicitly express the dependence on $\alpha$.
Note that, as is common practice [], when minimizing a function involving $q_{k}(W)$ with respect to $W$, we treat $\alpha$ as a constant. Consequently, we do not backpropagate the gradient with respect to $\alpha$.
To backpropagate through $q_{k}$, we employ the classical Straight-Through-Estimator (STE), described for completeness in [Appendix C](#A3).

### 3.4 Inducing approximate orthogonality to q k ​ ( W ) subscript 𝑞 𝑘 𝑊 q_{k}(W)

It is worth noting that, even when $W$ is orthogonal, the output $q_{k}(W)$ of the quantizer is generally not orthogonal. Research on Hadamard matrices suggests, in large dimensions, the difficulty of finding matrices that are both quantized and orthogonal [, ]. We anticipate that there is no direct method to
obtain a matrix close to $W$ that is both quantized and orthogonal.

As expressed by the bounds calculated below in ([3](#S3.E3)) and ([4](#S3.E4)), when $W$ is orthogonal, if $k$ is large enough, we expect $W_{q}=q_{k}(W)$ to remain close to orthogonality. However, these bounds provide satisfactory guarantees only when $n_{h}\ll 2^{k-1}$. Unfortunately, this condition is not met in the scenarios of interest. While we will observe in the experiments that it works in practice, the worst-case bounds do not guarantee that imposing orthogonality on $W$ will result in a quantized matrix $q_{k}(W)$ that is sufficiently close to orthogonality.

#### Evaluating the approximate orthogonality of q k ​ ( W ) subscript 𝑞 𝑘 𝑊 q_{k}(W)

Assume $W$ is orthogonal and denote $H=W_{q}-W$, where $W_{q}=q_{k}(W)$. Since $W$ is orthogonal, we have $\|WH^{\prime}\|_{F}=\|H^{\prime}\|_{F}=\|H\|_{F}$, and we obtain:

$$ $\displaystyle\|W_{q}W_{q}^{\prime}-I\|_{F}$ $\displaystyle=$ $\displaystyle\|(W+H)(W+H)^{\prime}-WW^{\prime}\|_{F}$ $\displaystyle=$ $\displaystyle\|WH^{\prime}+HW^{\prime}+HH^{\prime}\|_{F}$ $\displaystyle\leq$ $\displaystyle 2\|WH^{\prime}\|_{F}+\|HH^{\prime}\|_{F}$ $\displaystyle\leq$ $\displaystyle 2\|H\|_{F}+\|H\|^{2}_{F}.$ $$

Considering that, with the quantization scheme defined in [Section 3.3](#S3.SS3), we have $\|H\|_{\max}\leq\frac{\alpha}{2^{k-1}}=\frac{\|W\|_{\max}}{2^{k-1}}$ and noting that, since $W$ is orthogonal, $\|W\|_{\max}\leq 1$, we have the inequalities $\|H\|_{F}\leq n_{h}\|H\|_{\max}\leq\frac{n_{h}}{2^{k-1}}$. This leads to

$$ $\|W_{q}W_{q}^{\prime}-I\|_{F}\leq 2\frac{n_{h}}{2^{k-1}}+\left(\frac{n_{h}}{2^{k-1}}\right)^{2}.$ (3) $$

Similarly, using that $\sigma_{\max}(H)\leq n_{h}\|H\|_{\max}\leq\frac{n_{h}}{2^{k-1}}$ and that $W$ is orthogonal, we obtain

$$ $1-\frac{n_{h}}{2^{k-1}}\leq\sigma_{\min}(W_{q})\quad\mbox{and}\quad\sigma_{\max}(W_{q})\leq 1+\frac{n_{h}}{2^{k-1}}.$ (4) $$

## 4 Quantized RNNs with approximate orthogonality constraints

In this section, we describe
the four proposed strategies to build QORNN that are evaluated in [Section 5](#S5). Each strategy is presented in one of the following subsections.

### 4.1 Post-Training Quantization (PTQ-projUNN)

For all values of $k$, the weights with approximate orthogonality constraints, and quantized using $k$ bits, are $(q_{k}(W),q_{k}(U),V,b_{o})$, where $(W,U,V,b_{o})$ is
the full-precision parameters obtained using the projUNN-D algorithm [] for solving

$$ $\left\{\begin{array}[]{l}\underset{(W,U,V,b_{o})}{\min}~{}L(W,U,V,b_{o})\\ W\mbox{ is orthogonal,}\end{array}\right.$ $$

where $L$ is the learning objective.

Figure: Figure 2: Adding task experiments for $T=750$, several quantization bitwidths $k$, and $n_{h}=170$: (a) PTQ-projUNN test error; (b) STE-projUNN, STE-Bjorck and projUNN (FP) test errors. LSTM (FP) test errors are identical to those of projUNN (FP); (c) Ratio $\sigma_{\min}(W_{q})/\sigma_{\max}(W_{q})$.
Refer to caption: /html/2402.04012/assets/x3.png

### 4.2 Penalized STE (STE-pen)

A Quantized-Aware-Training (QAT) strategy is applied to directly learn quantized weights with approximate orthogonality constraints $(q_{k}(W),q_{k}(U),V,b_{o})$, for a given $k$. $(W,U,V,b_{o})$ are obtained using an implementation of the Straight-Through Estimator (STE) to solve the following optimization problem:

$$ $\underset{(W,U,V,b_{o})}{\min}~{}L(q_{k}(W),q_{k}(U),V,b_{o})+\lambda R(q_{k}(W)).$ (5) $$

Here, $L$ represents the learning objective, $R$ is the regularization term enforcing orthogonality as defined in ([2](#S3.E2)), and $\lambda$ is a parameter that balances the trade-off between minimizing $L$ and $R$. A similar model has been tested for vision tasks in []. Results of experiments with another regularization term are reported in [Appendix D](#A4).

### 4.3 Projected STE (STE-projUNN)

A QAT strategy is applied to directly learn quantized weights with approximate orthogonality constraints $(q_{k}(W),q_{k}(U),V,b_{o})$, for a given $k$. $(W,U,V,b_{o})$ are obtained using ProjUNN-D projected gradient descent algorithm solving the following optimization problem:

$$ $\left\{\begin{array}[]{l}\underset{(W,U,V,b_{o})}{\min}~{}L(q_{k}(W),q_{k}(U),V,b_{o})\\ W\mbox{ is orthogonal,}\end{array}\right.$ (6) $$

where $L$ is the learning objective.
In the projected gradient descent algorithm, the gradients are computed using backpropagation and the STE, and the projections onto the Stiefel manifold are computed using $P_{\text{projUNN}}$.

### 4.4 STE with P Björck subscript 𝑃 Björck P_{\text{Björck}} (STE-Björck)

A QAT strategy is applied to directly learn quantized weights with approximate orthogonality constraints $(q_{k}(P_{\text{Björck}}(W)),q_{k}(U),V,b_{o})$, for a given $k$. Inspired by [], $(W,U,V,b_{o})$ are obtained using the differentiable surjective mapping onto the Stiefel manifold $P_{\text{Björck}}$, and solve the optimization problem:

$$ $\underset{(W,U,V,b_{o})}{\min}~{}L(q_{k}(P_{\text{Björck}}(W)),q_{k}(U),V,b_{o}),$ $$

where $L$ is the learning objective. As already explained, since $P_{\text{Björck}}$ is surjective onto the Stiefel manifold, solving this problem is equivalent to solving ([6](#S4.E6)). However, the reformulation leads to a different algorithm. The gradients are also computed using backpropagation and
the STE.

## 5 Experiments

In this section, we present the results of the models described in [Section 4](#S4) on several standard sequential tasks: the adding task in [Section 5.1](#S5.SS1), the copy task in [Section 5.2](#S5.SS2), the permuted pixel-by-pixel MNIST (pMNIST) task in [Section 5.3](#S5.SS3), and the next character prediction for the Penn TreeBank dataset in [Section 5.4](#S5.SS4). Three of these tasks are designed to be challenging because they rely on long-term dependencies within the sequences, making them well-suited for ORNNs. The fourth task pertains to a language model problem characterized by shorter-term dependencies.

To assess the performance of the QORNN, we also provide, in
[Section 5.1](#S5.SS1), [5.2](#S5.SS2), [5.3](#S5.SS3), and [5.4](#S5.SS4),
the performances of two full-precision RNNs:

- •
LSTM [] of the same hidden size as the quantized models (except for Penn TreeBank, see [Section 5.4](#S5.SS4)), referred to as LSTM (FP).
- •
ORRNs of the same hidden size as the quantized models, obtained using the projUNN-D algorithm [], referred to as projUNN-D (FP).

Additionally, we include the performance corresponding to random guessing, referred to as the naive baseline.

As recommended in [], we utilize the RMSprop optimizer for training ProjUNN-D. The classical Adam optimizer [] is employed for all other models.
Additional parameters can be found in [Appendix E](#A5) to [H](#A8).

### 5.1 Adding task

Figure: Figure 3: Copy task experiments for $T=1000+20$, several quantization bitwidths $k$, and $n_{h}=256$: (a) PTQ-projUNN test error; (b) STE-projUNN, STE-Bjorck and projUNN test errors. As reported in [], LSTM (FP) settles for the naive baseline; (c) Ratio $\sigma_{\min}(W_{q})/\sigma_{\max}(W_{q})$.
Refer to caption: /html/2402.04012/assets/x6.png

We consider the Adding task as described in []. In this task, the input to the RNN is a time series $(x_{t})_{t=1}^{T}\in(\mathbb R^{2})^{T}$. Denoting for all $t$, $x_{t}=(x[0]_{t},x[1]_{t})$, $(x[0]_{t})_{t=1}^{T}$ consists of random scalars sampled independently and uniformly from the interval $[0,1]$, while $(x[1]_{t})_{t=1}^{T}$ consists of zeros except for two randomly selected entries set to $1$. The output is $\sum_{t}x[0]_{t}\cdot x[1]_{t}$. As $T$ increases, this task evolves into a problem that requires longer-term memory. The naive baseline mean squared error (MSE) is approximately $0.167$. More details are given in [Appendix E](#A5).

We follow [] for most settings and consider $T=750$, and $n_{h}=170$. Learning curves and results for $n_{h}=400$ are described in the [Appendix E](#A5), leading to similar conclusions. The activation function $\sigma$ is the Rectified Linear Unit (ReLU), and $\sigma_{o}$ is the identity. The recurrent weight matrix is initialized to the identity matrix $I$. We performed experiments for each of the four proposed strategies– PTQ-projUNN, STE-pen, STE-projUNN, and STE-Bjorck – and for every $k\in\llbracket 2,9\rrbracket$.

Note that, when learning with projUNN, the recurrent weight matrix remains very close to the identity during the learning process. Since the quantization of such matrices would result in reverting to the identity matrix, we have modified the quantization scheme for this experiment and the PTQ-projUNN and STE-projUNN strategies . The quantized matrix is defined as $W_{q}=I+q_{k}(W-I)$.

Confirming the challenging and unstable nature of quantizing ORNNs [, , ], [Figure 2](#S4.F2)-a illustrates that PTQ-projUNN is only feasible for a large bitwidth, $k\geq 10$.

The STE-pen method fails to learn, regardless of the bitwidth.
In [Figure 2](#S4.F2)-b, we observe that both STE-Bjorck and STE-projUNN successfully learn the task, achieving a lower MSE
than the naive baseline, even with only 2 or 3 bits.
However, the STE-projUNN strategy is more challenging to learn than STE-Bjorck. This is possibly due to the resulting matrices being close to the identity.

Since the orthogonal property is essential for learning long-term dependencies, we examine the ratio between the minimum and maximum singular values of $W_{q}$ in [Figure 2](#S4.F2)-c. Astonishingly, STE-Bjorck is able to initiate learning for this task with a low ratio. However, as expected, achieving more precise learning involves matrices that are close to orthogonal, i.e. for bitwidths $k\geq 5$.

### 5.2 Copy task

Figure: Figure 4: pMNIST experiments for several quantization bitwidths $k$, and $n_{h}=170$: (a) PTQ-projUNN test accuracy; (b) Test accuracy for all approaches. LSTM (FP) test accuracy is identical to that of projUNN (FP); (c) Ratio $\sigma_{\min}(W_{q})/\sigma_{\max}(W_{q})$.
Refer to caption: /html/2402.04012/assets/x9.png

Figure: Figure 5: Penn TreeBank experiments for several quantization bitwidths $k$, and $n_{h}=1024$: (a) PTQ-projUNN BPC; (b) BPC for all approaches. LSTM (FP) is given for a hidden size of $256$, yielding better results; (c) Ratio $\sigma_{\min}(W_{q})/\sigma_{\max}(W_{q})$.
Refer to caption: /html/2402.04012/assets/x12.png

We build RNNs solving the copy task as described in [], based on the setup outlined by []. This task is known to be a difficult long-term memory benchmark, that classical LSTMs struggle to solve [, ]. The input is a sequence of length $T=T_{0}+20$, where the initial 10 elements constitute a sequence for the network to memorize, followed by a marker at $T_{0}+11$. The RNN’s objective is to generate a sequence of the same length, with the last ten elements replicating the initial 10 elements of the input sequence. More details are given in [Appendix F](#A6).

The output activation $\sigma_{o}$ is the softmax, and the prediction error is measured using the average cross-entropy. The naive baseline has an expected cross-entropy of $\frac{10\log 8}{T_{0}+20}$.

As in  [], we conducted the experiments for $T_{0}=1000$ timesteps, with ORNNs of size $n_{h}=256$. Details on the hyperparameters, learning curves, results for $n_{h}=190$ and $T_{0}=2000$ are provided in the [Appendix F](#A6).

All the results are on [Figure 3](#S5.F3). The performance of projUNN (FP) is significantly degraded by PTQ-projUNN for $k\leq 9$. STE-pen also fails to learn, regardless of the bitwidth.
As reported by [], LSTM also remains stuck at the naive baseline. Both STE-projUNN and STE-Bjorck require $k\geq 5$
to converge (Y-axis in [Figure 3](#S5.F3)-b is in log scale).
We observe in [Figure 3](#S5.F3)-c that the conditioning of the quantized recurrent weight matrix has a direct impact on the performance of the STE-projUNN and STE-Bjorck. A good conditioning is not sufficient for PTQ-projUNN.

### 5.3 Permuted pixel-by-pixel MNIST (pMNIST)

This task is also considered a challenging long-term memory problem. Here, data examples are the $28\times 28$ images from the MNIST dataset, where each image is flattened to a $784$-long sequence of $1$-dimensional pixels (normalized values in $[0,1]$), and the pixels are randomly shuffled according to a fixed permutation.
The model has to predict the hand-written digit class (10 outputs).

In this section, we fix $n_{h}=170$ for all algorithms. Results for STE-pen with another regularization term are in the [Appendix D](#A4). We use the ReLU activation with the STE-pen and STE-Bjorck strategies, and as recommended in [] the modReLU activation with the STE-projUNN, projUNN (FP) and PTQ-projUNN strategies (see [Appendix G](#A7) for details). For each algorithm, we test all bitwidths $k\in\llbracket 2,8\rrbracket$. We measure performances using the accuracy and compare the results with those of LSTM (FP): a trained LSTM with a hidden size of $n_{h}=170$ and full-precision weights.

For STE-pen, mere quantization of the recurrent weight matrix leads to significant spectral norm alteration, hindering the learning process. To avoid this problem, we found it useful to normalize the matrix by its spectral norm after each quantization step.

In [Figure 4](#S5.F4)-b, we observe that STE-Bjorck outperforms all other strategies for all bitwidths, and yields better results than the LSTM (FP) and projUNN (FP) even for small bitwidths ($k\geq 4$). As for the Adding task, STE-Bjorck is able to learn significant information (accuracy $\geq 0.8$), even when the condition number is small ($\sigma_{min}(W_{q})/\sigma_{max}(W_{q})\leq 0.5$, [Figure 4](#S5.F4)-c). For $k\geq 5$, STE-Bjorck achieves results comparable to those reported in [, ], which currently represent the state-of-the-art in orthogonal and unitary recurrent networks. We observe that the STE-projUNN strategy produces results similar to projUNN-D (FP) and LSTM (FP), though requiring a bitwidth of $7$ or more, which corresponds to a high orthogonality level ($\sigma_{min}(W_{q})/\sigma_{max}(W_{q})\geq 0.8$). Again, the PTQ-projUNN approach only matches the performance of projUNN-D (FP) and LSTM (FP) for bitwidths $k\geq 8$, confirming the difficulty of ORNN quantization. The STE-pen approach never achieves $80\%$ accuracy.

### 5.4 Character level Penn TreeBank

We provide results of QORNNs on a language modeling task. The Penn TreeBank dataset [] (PTB) is a corpus of sentences of $50$ different characters.
The goal of the task is to predict the next character based on the preceding ones (further details can be found in [Appendix H](#A8)).

All experiments described in this section are for $n_{h}=1024$, except for LSTM (FP) for which we set $n_{h}=256$ to avoid overfitting. Again, our learning approaches are tested for all bitwidths $k\in\llbracket 2,8\rrbracket$. The models are evaluated with the Bit Per Character measure (BPC).

The results for this task are reported in [Figure 5](#S5.F5). The STE-Bjorck approach allows beating LSTM (FP) for small bitwidths ($k\geq 4$). The STE-projUNN achieves similar performances as projUNN (FP) for $k=8$. Interestingly, this task is the only one for which STE-pen comes close to the LSTM (FP) for $k=7$ and $k=8$. This could be attributed to the task not relying on dependencies over an extended delay compared to the others. PTQ-projUNN reaches results comparable to the full-precision version only for $k\geq 8$.

## 6 Conclusion and perspectives

In this paper, we examined the impact of bitwidth in the quantization of ORNNs using four QAT and PTQ approaches, demonstrating empirically the advantages of using QAT methods over PTQ.
The proposed STE-Bjorck approach, described in [Section 4.4](#S4.SS4), demonstrates compelling performance even for small bitwidths, paving the way for the resource-efficient implementation of approximately orthogonal RNNs and prompting a more in-depth analysis.

Future work on QORNNs could therefore focus on developing alternative learning approaches and quantization schemes, creating methods for quantizing both weights and activations, and implementing them on dedicated hardware.

## Acknowledgments and Disclosure of Funding

This work has benefited from the AI Interdisciplinary Institute ANITI, which is funded by the French “Investing for the Future – PIA3” program under the Grant agreement ANR-19-P3IA-0004. The authors gratefully acknowledge the support of the DEEL project.(^4^44[https://www.deel.ai/](https://www.deel.ai/))

## Appendix A Memorization and stability, vanishing and exploding gradient

For a large $T$, if the largest singular value $\sigma_{max}$ of the weight matrix $W$ is smaller than $1$, the initial entries of the input $(x_{t})_{t=1}^{T}$ cannot be effectively retained in the hidden state $h_{T}$. This prevents the consideration of long-term dependencies. Conversely, still considering large $T$, if the smallest singular value $\sigma_{min}$ of $W$ is greater than $1$, each multiplication by $W$ in ([1](#S3.E1)) increases the magnitude of $h_{t}$, and the norm $\|h_{t}\|$ may tend towards infinity, leading to instability. For memorization and stability issues, it is desirable for the singular values of $W$ to remain close to $1$.

We arrive at the same conclusion when attempting to mitigate issues related to vanishing and exploding gradients. As indicated in [] and echoed in subsequent literature on URNNs, denoting $L$ the loss function, we find that:

$$ $\displaystyle\frac{\partial L}{\partial h_{t}}$ $\displaystyle=$ $\displaystyle\frac{\partial L}{\partial h_{T}}\frac{\partial h_{T}}{\partial h_{t}}$ $\displaystyle=$ $\displaystyle\frac{\partial L}{\partial h_{T}}\prod_{i=t}^{T-1}\frac{\partial h_{i+1}}{\partial h_{i}}$ $\displaystyle=$ $\displaystyle\frac{\partial L}{\partial h_{T}}\prod_{i=t}^{T-1}D_{i}W^{\prime},$ $$

where $D_{i}=\operatorname{diag}\bigl{(}\sigma^{\prime}(Wh_{i-1}+Ux_{i})\bigr{)}$ is the Jacobian(^5^55Since it is not central to our article, we assume that all the entries of $Wh_{i-1}+Ux_{i}$ are non-zero, ensuring that the Jacobian and $\sigma^{\prime}$ are well-defined.) matrix of $\sigma$ evaluated at the pre-activation point and $W^{\prime}$ is the transpose of $W$. If all the singular values of $W$ are less than $1$, those of $D_{i}W^{\prime}$ are as well, causing the norm of $\frac{\partial L}{\partial h_{t}}$ to rapidly approach 0 0 as $t$ decreases—resulting in the vanishing gradient problem. Conversely, if some singular values of $W$ are greater than $1$, depending on the activation patterns and $\frac{\partial L}{\partial h_{T}}$, the norm may explode, leading to the exploding gradient problem. To mitigate these phenomena, it is desirable for the singular values of $W$ to remain close to $1$. In other words, we aim for $W$ to be orthogonal or at least approximately orthogonal.

## Appendix B The Björck algorithm

Björck algorithm [] aims to minimize the regularization term $R$. As described in [], the initialization is done with the matrix $A_{0}=\frac{1}{\sigma_{\text{max}}(W)}W$, where $\sigma_{\text{max}}(W)$ is the largest singular value of $W$, computed using the power iteration for a fixed number of iterations. Then it applies a fixed and sufficiently large number of iterations, in practice $15$, of the following operation:

$$ $A_{k+1}=A_{k}\left(I+\sum_{i=1}^{p}(-1)^{p}\binom{-\frac{1}{2}}{p}Q_{k}^{p}\right)$ $$

where $Q_{k}=I-A^{\prime}_{k}A_{k}$ and $\binom{z}{p}=\frac{1}{p!}\prod_{i=0}^{p-1}(z-i)$. As described in [], we take $p=1$. In this case, the Björck algorithm corresponds to several iterations of the gradient descent algorithm minimizing $R$:

$$ $A_{k+1}=A_{k}-\frac{1}{2}A_{k}(A_{k}^{\prime}A_{k}-I)=\frac{3}{2}A_{k}-\frac{1}{2}A_{k}A_{k}^{\prime}A_{k},$ $$

initialized at $A_{0}=\frac{1}{\sigma_{\text{max}}(W)}W$.

We compute $\left.\frac{\partial P_{\text{Björck}}}{\partial W}\right|_{W}$ using standard backpropagation but treat $\sigma_{\text{max}}(W)$ as a constant.

## Appendix C The straight-through-estimator

Considering $\alpha$ as fixed, the mapping $W\longmapsto q_{k}(W)$ is piecewise constant. Its gradient at $W$, denoted as $\left.\frac{\partial q_{k}}{\partial W}\right|_{W}$, is either undefined or 0 0. This issue is well-known in quantization-aware training, which aim to minimize an objective $L(q_{k}(W))$ with respect to $W$, where $W_{q}\longmapsto L(W_{q})$ is the learning loss. Backpropagating the gradient using the chain rule

$$ $\left.\frac{\partial L\circ q_{k}}{\partial W}\right|_{W}=\left.\frac{\partial L}{\partial W_{q}}\right|_{q_{k}(W)}\left.\frac{\partial q_{k}}{\partial W}\right|_{W}$ $$

is either not possible or results in a null gradient in this context.

To address this issue, backpropagation through the quantizer is performed using the straight-through estimator (STE) [, , ]. The STE approximates the gradient using

$$ $\left.\frac{\partial L\circ q_{k}}{\partial W}\right|_{W}\approx\left.\frac{\partial L}{\partial W_{q}}\right|_{q_{k}(W)}.$ $$

When minimizing models that involve $q_{k}(W)$, we consistently approximate the gradient using the STE and treat $\alpha$ as if it were independent of $W$.

## Appendix D Comparizon of soft-orthogonal regularizers

Figure: Figure 6: pMNIST: Test accuracy and ratio $\sigma_{min}(q_{k}(W))/\sigma_{max}(q_{k}(W))$ for STE-pen with different soft-orthogonality regularizers: ‘SO’ corresponds to the regularizer $R^{SO}(W)=\|WW^{\prime}-I\|_{F}^{2}$; ‘Spectral’ corresponds to the regularizer $R^{spectral}=\sum_{i=1}^{n_{h}}|\sigma_{i}-1|^{2}$.
Refer to caption: /html/2402.04012/assets/x15.png

In addition to the soft-orthogonality regularizer $R^{SO}=\|WW^{\prime}-I\|_{F}^{2}$, we tested another regularizer that we term the Spectral regularizer: $R^{spectral}(W)=\sum_{i=1}^{n_{h}}|\sigma_{i}-1|^{2}$, where $(\sigma_{i})_{i=1}^{n_{h}}$ represents the singular values of $W$. The computation of this regularizer and its gradient involves performing the singular value decomposition of $W$, which becomes computationally expensive for large hidden size values $n_{h}$.

We present the results of STE-pen with this regularizer on pMNIST and compare these results with those of the SO regularizer. In [Figure 6](#A4.F6), we display the accuracies and ratios $\sigma_{min}(q_{k}(W))/\sigma_{max}(q_{k}(W))$ for various hidden sizes $n_{h}$. Although the results for both regularizers are similar, the SO regularizer is computationally more efficient.

## Appendix E Complements on the Adding task experiments

#### Detailed task description:

The Adding task as described in [] defines as input two parallel data sequences of length $T$, concatenated in a time series in $(\mathbb R^{2})^{T}$. The first sequence consists of scalars sampled independently and uniformly from the interval $[0,1]$. The second sequence consists of zeros, except for two entries that are set to $1$. The positions of the first and second occurrences of $1$ are randomly selected, each following a uniform distribution over the intervals $\llbracket 1,T/2\rrbracket$ and $\llbracket T/2+1,T\rrbracket$, respectively. The output is the sum of the two scalars from the first sequence, located at the positions corresponding to the $1$s in the second sequence. As $T$ increases, this task transforms into a problem requiring longer-term memory. Naively predicting $1$ (the average value of the sum of two independent random variables uniformly distributed in $[0,1]$) for any input sequence yields an expected mean squared error (MSE) of $\approx 0.167$, serving as our naive baseline.

#### Hyperparameters:

We use as in [], 100000 training samples, and 2000 test samples.

As described in [], initialization is done with the identity matrix. For all approaches, we use ReLU as the activation function $\sigma$.

We do not detail hyperparameters for the STE-pen method here, as none of the tested configurations yields satisfactory results.

The initial learning rate is $1e-4$ for projUNN-D (i.e. projUNN (FP), PTQ-projUNN and STE-projUNN strategies), and $1e-3$ for STE-Bjorck. A divider factor of 32 is applied for recurrent weights update, as described in []. A learning rate schedule is applied by multiplying the learning rate by $0.94$ at each epoch.
We use RMSprop optimizer for projUNN-D (i.e. projUNN (FP), PTQ-projUNN and STE-projUNN strategies) method, applying the projUNN-D algorithm with the LSI sampler and a rank 1 (as described in []). For STE-Bjorck we use the classical Adam optimizer. Batch size is set to 50.

The training spanned 50 epochs.

For LSTM (FP), our results align with those reported in [], demonstrating its capability to learn this task even over $750$ time steps.

#### Complementary results:

We present on [Figure 7](#A5.F7) the evolution of test loss during the training for STE-projuNN and STE-Bjorck and several bitwidths. The curves verify that STE-Bjorck learns the adding-task with greater ease.

Figure: Figure 7: Evolution of Test Loss During Training for the Adding task with $n_{h}=170$. (Left) STE-projUNN ; (Right) STE-Bjorck.
Refer to caption: /html/2402.04012/assets/x21.png

We present on [Figure 8](#A5.F8) the test accuracy for a larger hidden size $n_{h}=400$, for PTQ-projUNN, STE-projUNN, STE-Bjorck, and projUNN (FP). Conclusions are similar to the ones established for $n_{h}=170$ for PTQ-projUNN, STE-projUNN and STE-Bjorck. When compared to the results displayed on [Figure 2](#S4.F2), the results of STE-projUNN and STE-Bjorck improve. In particular, STE-Bjorck significantly beats the naive baseline even for $k=2$.

Figure: Figure 8: Adding task results for $T=750$ and $n_{h}=400$.
Refer to caption: /html/2402.04012/assets/x23.png

## Appendix F Complements on the Copy task experiments

#### Detailed task description:

This task is the same experiment as in [], based on the setup defined by [, ]. The copy task is known to be a difficult long-term memory benchmark, that classical LSTMs struggle to solve [, ].

Here, input data examples are in the form of a sequence of length $T=T_{0}+20$, whose first $10$ elements represent a sequence for the network to memorize and copy. We use a vocabulary $V=\{a_{i}\}_{i=1}^{p}$ of $p=8$ elements, plus a blank symbol $a_{0}$ and a delimiter symbol $a_{p+1}$. Each symbol $a_{i}$ is one-hot encoded, resulting in an input time series where $n_{i}=10$ and an output time series where $n_{o}=9$ ($a_{p+1}$ is not a target value).

An input sequence has its first $10$ elements sampled independently and uniformly from $V$, followed by $T_{0}$ occurrences of the element $a_{0}$. Then, $a_{p+1}$ is placed at position $T_{0}+11$, followed by another $9$ occurrences of $a_{0}$. The RNN is tasked with producing a sequence of the same length, $T_{0}+20$, where the first $T_{0}+10$ elements are set to $a_{0}$, and the last ten elements are a copy of the initial $10$ elements of the input sequence.

The naive baseline consists of predicting $T_{0}+10$ occurrences of $a_{0}$ followed by $10$ elements randomly selected from $V$. Such a strategy results in an expected cross-entropy of $\frac{10\log 8}{T_{0}+20}$.

#### Hyperparameters:

We use as in [], 512000 training samples, and 100 test samples.

As described in [], for projUNN-D (i.e. projUNN (FP), PTQ-projUNN and STE-projUNN strategies), we use Henaff initialization []. For all approaches, we use modReLU as the activation function $\sigma$ [].

As for the Adding task, we do not detail hyperparameters for the STE-pen method here.

The initial learning rate is $7e-4$ for projUNN-D (i.e. projUNN (FP), PTQ-projUNN and STE-projUNN strategies), and $1e-4$ for STE-Bjorck. A divider factor of 32 is applied for recurrent weights update, as described in []. A learning rate schedule is applied by multiplying the learning rate by $0.9$ at each epoch.
We use the RMSprop optimizer for projUNN-D (i.e. projUNN (FP), PTQ-projUNN and STE-projUNN strategies), applying the projUNN-D algorithm with the LSI sampler and a rank 1 (as described in []). For STE-Bjorck we use the classical Adam optimizer. Batch size is set to 128.

The training spanned 10 epochs.

For LSTM (FP) we report the results given by [], which indicates that it remains stuck at the naive baseline.

#### Complementary results:

We present on [Figure 9](#A6.F9) the evolution of test loss during the training for STE-projuNN and STE-Bjorck and several bitwidths.

Figure: Figure 9: Evolution of Test Loss During Training for the Copy task with $n_{h}=256$. (Left) STE-projUNN ; (Right) STE-Bjorck.
Refer to caption: /html/2402.04012/assets/x25.png

We present the results for the copy task in [Figure 10](#A6.F10) with $T_{0}=1000$ time steps and $n_{h}=190$. The conclusions drawn are similar to those depicted in [Figure 3](#S5.F3), where $T_{0}=1000$ and $n_{h}=256$. The main difference between the results in Figure [Figure 10](#A6.F10) for $n_{h}=190$ and [Figure 3](#S5.F3) for $n_{h}=256$ lies in the fact that, similar to the adding task, a smaller value of $n_{h}$ allows achieving comparable performance but with a larger bitwidth $k$. There appears to be a trade-off that needs to be optimized between hidden size and bitwidth.

Figure: Figure 10: Copy task results for $T=1000+20$ and $n_{h}=190$.
Refer to caption: /html/2402.04012/assets/x27.png

We present the results for the copy task in [Figure 11](#A6.F11) with $T_{0}=2000$ time steps and $n_{h}=256$. This task proves to be more challenging to learn; both STE-projUNN and STE-Bjorck only achieve the naive baseline with 6-bit quantization. It seems likely that increasing the hidden size $n_{h}$ would allow for a reduction in bitwidth.

Figure: Figure 11: Copy task results for $T=2000+20$ timestep with $n_{h}=256$.
Refer to caption: /html/2402.04012/assets/x29.png

## Appendix G Complements on the pMNIST task experiments

#### Hyperparameters:

We use the $60,000$ training samples and $10,000$ test samples from the MNIST dataset.

As described in [], we employ a random orthogonal matrix initialization for the recurrent weight matrix. The activation function $\sigma$ is ReLU for STE-Bjorck and STE-pen and LSTM (FP). We utilize modReLU [] for projUNN-D (i.e. projUNN (FP), PTQ-projUNN and STE-projUNN strategies), as performances achieved with ReLU are inferior.

The initial learning rate is $1e-3$ for all strategies and weights. It remains constant for STE-pen and LSTM (FP). A learning rate schedule is applied by multiplying the learning rate by $0.2$ every $60$ epochs for projUNN-D (i.e. projUNN (FP), PTQ-projUNN and STE-projUNN strategies) and STE-Bjorck.

We utilize the RMSprop optimizer for projUNN-D (i.e. projUNN (FP), PTQ-projUNN and STE-projUNN strategies), implementing the projUNN-D algorithm with the LSI sampler and a rank of $1$ (as described in []). For STE-Bjorck, STE-pen and LSTM (FP), we employ the classical Adam optimizer.

For STE-pen, the regularization parameter $\lambda$, which governs the trade-off between optimizing the learning objective and the regularizer (see [Equation 5](#S4.E5)), is set to $1e-1$.

The batch size is set to $64$ for STE-pen and LSTM (FP). For all other approaches, it is set to 128.

The training spanned 200 epochs.

#### Complementary results:

We present on [Figure 12](#A7.F12) the evolution of test accuracy during the training for STE-projuNN and STE-Bjorck and several bitwidths. Learning is easier with STE-Bjorck.

Figure: Figure 12: Evolution of the Accuracy During Training for pMNIST with $n_{h}=170$. (Left) STE-projUNN ; (Right) STE-Bjorck.
Refer to caption: /html/2402.04012/assets/x30.png

On [Figure 13](#A7.F13), we illustrate the accuracy evolution during training for STE-pen and various bitwidths with $n_{h}=170$ and $n_{h}=360$.

Figure: Figure 13: Evolution of the Accuracy During Training for pMNIST with STE-pen (Left) $n_{h}=170$ (Right) $n_{h}=360$.
Refer to caption: /html/2402.04012/assets/x32.png

Figure: Figure 14: pMNIST results for $n_{h}=360$
Refer to caption: /html/2402.04012/assets/x34.png

We present the results for pMNIST in [Figure 14](#A7.F14) with a larger hidden size, $n_{h}=360$. The qualitative conclusions drawn are similar to those depicted in [Figure 4](#S5.F4) for $n_{h}=170$. Similar to the Adding task and the copy task, the results for the larger hidden size are superior. For instance, PTQ-projUNN achieves an accuracy above $80\%$ for bitwidth $k=6$, while the case of $n_{h}=170$ required 8 bits to reach comparable results (see [Figure 4](#S5.F4)-a).

## Appendix H Complements on the Character level Penn TreeBank experiments

#### Detailed task description:

The Penn TreeBank dataset consists of sequences of characters, utilizing an alphabet of $50$ different characters. The dataset is divided into $5017$K training characters, $393$K validation characters, and $442$K test characters. Sentences are padded with a blank value when their size is less than the fixed sequence length of $150$ characters. The task aims to predict the next character based on the preceding ones. Formally expressed as time series, each sentence represents an input time series of size $n_{i}=50$ (since characters are one-hot encoded) with $T=150$, and the corresponding output time series is identical to the input time series but shifted by one character.

The models are evaluated using the Bit Per Character measure (BPC), which is the base-$2$ logarithm of the likelihood on masked outputs (to exclude padding values for evaluation).

#### Hyperparameters:

As described in [], we take a random orthogonal matrix initialization for the recurrent weights. We use ReLU as the activation function $\sigma$ for STE-Bjorck and STE-pen. For projUNN-D (i.e., projUNN (FP), PTQ-projUNN and STE-projUNN strategies), we utilize modReLU [] as the activation function, as performances achieved with ReLU were found to be inferior.

The initial learning rate is set to $1e-3$ for all strategies and weight types. It remains constant for STE-pen and LSTM (FP). A divider factor of 8 is applied to recurrent weight updates. A learning rate schedule is implemented by multiplying the learning rate by $0.2$ every 20 epochs for projUNN-D (i.e., projUNN (FP), PTQ-projUNN, and STE-projUNN strategies) as well as for STE-Bjorck.

We employ the RMSprop optimizer for projUNN-D, utilizing the projUNN-D algorithm with the LSI sampler and a rank 1, as described in []. For STE-Bjorck, STE-pen, and LSTM (FP), we use the classical Adam optimizer.

The regularization parameter $\lambda$ for STE-pen is fixed to $1e-1$.

The batch size is set to $100$ for STE-pen and LSTM (FP). For all other approaches, it is set to $128$.

The training spanned 50 epochs.

#### Complementary results:

We present on [Figure 15](#A8.F15) the evolution of validation BPC during training for STE-pen and several bitwidths with $n_{h}=1024$ and $n_{h}=2048$.

Figure: Figure 15: Evolution of the BPC During Training for Penn TreeBank with STE-pen (Left) $n_{h}=1024$ (Right) $n_{h}=2048$.
Refer to caption: /html/2402.04012/assets/x36.png

Figure: Figure 16: Penn TreeBank results for $n_{h}=2048$. The STE-projUNN curve has no dots at $k=2$, $k=4$, $k=7$, indicating that the training diverged.
Refer to caption: /html/2402.04012/assets/x38.png

[Figure 16](#A8.F16) presents supplementary results for a larger hidden size of $n_{h}=2048$. While most results are similar to those obtained with $n_{h}=1024$, it is worth noting that STE-projUNN trainings did not converge for bitwidths $4$ and $7$.

## Peer Reviews

confidence: 4
contribution: 1
initial_rating: 3
presentation: 3
questions: * It is unclear from the paper why you quantize U but not V. Could you please elaborate on that choice?
* It is unclear to me why the ProjUNN is much better in the copy task but worth on MNIST and PTB (both quantized and unquantized model). Do you have any idea or intuition why this is the case?


**Comments on presentation:**
* $\sigma$ is a bit overuse ($\sigma, \sigma_o$ but also $\sigma_{min}, \sigma_{max}$ for eigenvalues, …)
* The authors reuse $T$ in line 258 again as a power of the weight matrix, which seem based on the text has not any connection to the sequence length T. I suggest the authors either use a different symbol or explain why to the power of $T$ would be relevant here.
    * I can see that this likely comes from the sequence length $T$, though given there is activation function $\sigma$ (and $Ux$) there, it is unclear why this would be important or relate to the final task loss. If this is the case, please elaborate.
* Many equations do not have numbers which makes it hard for readers to refer to them (even if authors do not refer themselves to some equations, a future reader might want to do so). Therefore I suggest to follow common best practices and number all equations that are not in-line.
soundness: 2
strengths: * The investigation on weight quantization effects on ORNNs is interesting and insightful (sec 3.4).
* Based on the experiments the proposed QRNNs (especially with STE-Bjorck) seem to perform well, even till 5-6 bits.
* The paper is clearly written and easy to follow (except a few minor points).
summary: In this paper, the authors study the quantization of orthogonal recurrent neural networks (ORNNs). They first investigate the impact of quantization on the orthogonality, including effects on the singular values of the quantized weights and deriving bounds for them. Then the authors propose and investigate two flavors of quantized orthogonal recurrent neural networks (QORNNs) which combine traditional ORNN training with quantization-aware training (QAT). In the experiments they show that QORNNs are competitive with SOTA ORNN, LSTM and FastRNN on a various benchmarks such as copying, flavors of MNIST and PTB.
weaknesses: * The biggest shortcoming of this paper is the limited novelty. Several points regarding this:
    * The authors combine two off the shelf ORNN training algorithms with the most simple (and arguably outdates, see later) flavor of QAT. In other words, they add $q_k(W_i)$ to these algorithms (cf line 3, 4 in algorithms 1, 2, respectively) and assume STE.
    * While I found the investigation in sec 3.4 interesting (see above), I would have expected that these insights come back in their algorithm design (or at least that the authors evaluate such metrics for their proposed approach, look at question whether these metrics in practice correlate with QORNN performance etc).
* On the quantization side, they seem to miss/ignore a lot of innovation that happened in the last 5ish years which could help to potentially have much better performance at low bit-widths. Most importantly:
    * They argue keeping the scale fixed is common practice (line 241/242). Since the introduction of LSQ [1] this is long not common practice anymore.
    * It is unclear to me why the authors not consider per-channel weights. As per-channel weights still work with full fixed-point/integer arithmetic [2], this is supported by almost any HW and commonly used by most quantization literature in the past years. This adds an additional degree of freedom that might be very helpful for ORNNs as by changing the scale ($\alpha$), as one could ensure that rows (or columns, depending on notation) still have a norm of 1 which seems important (cf sec 3.2).
* The proposed QORNNs are actually not orthogonal as the name or text suggest. Only the latent weights ($W_i$) are orthogonal, but the actual quantized weights used for inference ($q_k(W_i)$) are only approximately orthogonal. As the authors themselves show (cf figure 1, sec 3.4), this doesn’t give any guarantees and could be detrimental.
* As the paper positions itself more as ‘explorative’ (and QAT contribution is very limited), I would expect that they also more closely explore PTQ approaches. There are several degrees of freedom that are unexplored, e.g. setting the correct scale (alpha) or applying/adapting common PTQ algorithms such as AdaRound [3] or GPTQ [4].
* Minor:
    * The experimental evaluation is limited to only ‘toy-sized’ datasets/tasks. 
    * While it is nice they obtain bounds for q_min/max, the established bounds are so loose that from a practical perspective such bounds are not useful (nor similar to the earlier study they are used to design or evaluate the algorithm).
    * I do miss a comparison to challenges in quantizing transformers or SSMs. While it is arguable whether comparing to transformers it out of the scope of such a paper (as the authors claim), at least discussing/comparing whether the challenges in ORNNs are similar or different to transformers/SSMs would be helpful (e.g. do they suffer from similar outliers as observed in transformers, cf. [5,6]). 
    * Regarding SSMs, there is some recent work that would be interesting to compare to [7, 8]. 

**References:**
* [1] Esser et al., ICLR 2020, Learned Step Size Quantization.
* [2] Nagel et al., 2021, A White Paper on Neural Network Quantization.
* [3] Nagel et al. ICML 2020, Up or Down? Adaptive Rounding for Post-Training Quantization.
* [4] Frantar et al., ICLR 2023, Gptq: Accurate post-training quantization for generative pre-trained transformers.
* [5] Bondarenko et al., EMNLP 2021, Understanding and Overcoming the Challenges of Efficient Transformer Quantization.
* [6] Dettmers et al., NeurIPS 2022, LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale.
* [7] Pierre et al., ES-FoMo 2024, Mamba-PTQ: Outlier Channels in Recurrent Large Language Models
* [8] Abreu et al, NGSM 2024, Q-S5: Towards Quantized State Space Models

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: 1) Please provide a more detailed description of the experimental environment.
2) What is the meaning of "STE-Bjorck or STE-projUNN" in Table 2? I think the experimental results of each model should be separated for clarity. This could be improved by separating the experimental results of each model into different columns.
3) Why is STE-projUNN absent from Table 3?
soundness: 2
strengths: The paper is easy to read, and the proposed QORNN is effective even at long-term dependency tasks.
summary: This paper proposes a Quantized Approximately Orthogonal Recurrent Neural Network (QORNN), which is the quantization of Orthogonal Recurrent Neural Network. To address the inherent instability of quantizing vanilla RNN and ORNN, two quantization-aware training strategies are adopted. The method achieves impressive results on a variety of standard benchmarks.
weaknesses: - There are awkward and missing citations throughout the paper. For example, the citation for fastGRNN should have been first on line 114 instead of line 135. Besides, I think the representation, such as "activations for LSTM Hou et al. (2017)" in line 105, "Penn TreeBank dataset Marcus et al. (1993) (PTB)" is awkward.
- There are some issues on writing (see minor issues and questions below)

Minor Issues
1) There are some minor points on writing:
- Line 90: “The reasons .. is” -> “The reasons .. are”
- Lines 122 and 321: footnotes are written incorrectly
- Footnote 4: “Sections 3.4” should be revised correctly
- Equation in line 203, footnote 5, caption of Table 3, and line 466: please add a comma to the end of the sentence
- Line 286: add a colon to the next of the bolded sentence
- Subtitle 3.4: “QORNN are” -> “QORNN is” or “QORNNs are”
- Tabels 1 and 2, “fromKiani et al. (2022)” -> “from Kiani et al. (2022)”
- Table 2, “sizes for Copy, MNIST” -> “sizes for Copy-task, sMNIST”
2) Are the words "steps", "power", "timesteps" and "length" the same meaning? Mixed terms can confuse the reader. I recommend revising them for clarity. Other examples include copy/copy-task, SSMs/SSM/SSSM, etc.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: * In Tables 1-2, could you explain what do you mean with “NU” (‘Not useful because of other figures’)?
* What is the memory increase during training for the proposed methods compared to FastRNN, LSTM and vanilla RNN?
* In Table 1, it would be nice if authors could also include accuracy for copy-task, as it is easier to interpret the differences compared to cross-entropy numbers.
* Any reasoning why STE-Björk is faster than FastRNN and FastGRNN on pMNIST in Table 14? It seems quite surprising given that at every optimizer step Björck procedure requires running 15 iterations of the recursion with subsequent backpropagation through this procedure. While it's not the case for some other tasks, providing a detailed analysis of the computational complexity or runtime breakdown for STE-Björk vs. FastRNN/FastGRNN might be quite insightful.
soundness: 2
strengths: * Seems fairly easy to implement.
* Authors thoroughly motivate and explain challenges of constructing and training ORNNs & instabilities caused by quantization. 
* A comparison of model sizes in resulting QORNN models vs. other methods.
summary: This paper explores the quantization of the weight matrices in Orthogonal Recurrent Neural Nets (ORNNs). Authors introduce and compare two strategies for constructing ORNNs or approximately orthogonal RNNs with quantized weights (QORNNs): STE-projUNN and STE-Björck. These strategies are extensions of two methods of constructing full-precision ORNNs, respectively projUNN and Björck, that employ quantization-aware training with Straight-through assumption (STE).

QORNNs are evaluated on a synthetic copy-task, PTB and few variants of MNIST (pMNIST, sMNIST) datasets and compared against their floating-point variants and other families of RNNs, including LSTM, GRU, fastRNN, fastGRNN. The most efficient models achieve results similar to state-of-the-art full-precision ORNN, LSTM and FastRNN on a variety of standard benchmarks, even with 3-bits quantization.
weaknesses: * The proposed methods seem very straightforward: combine the strategy of constructing ORNNs with STE, which is a standard and well-known technique in the quantization literature.
* L286-L300: authors derive bounds for approximate orthogonality of q(W) which they themselves state are too loose to be useful in practice. It would be quite insightful to track and report $||W_q W_q^T – I ||$ during training, to see if the reason of proposed method working well in practice is due to $q(W)$ being fairly close to being orthogonal or not.
* L079: authors claimed SotA results on pMNIST, however they did not compare against other 4-bit sequence-to-sequence models, for instance SSM models such as Mamba [1], transformer models such as LLaMA-3 [2] etc. 
* Considered benchmarks are very small by today standards. While most of them seem standard in ORNN literature, it would make a story more convincing if authors included some of the more recent real-world datasets and benchmarks. For instance, it would be insightful to evaluate the proposed methods on some of common reasoning language tasks (MMLU, HellaSwag, Winogrande).

[1] Gu et al., “Mamba: Linear-Time Sequence Modeling with Selective State Spaces”. ArXiV: 2312.00752

[2] Dubey et al., “The Llama 3 Herd of Models”. ArXiV: 2407.21783

---

confidence: 5
contribution: 1
initial_rating: 1
presentation: 4
questions: Why not further reduce the precision of activations by adopting static learned scales akin to LSQ or PACT?
soundness: 3
strengths: This a very well-written paper with an extensive literature review, a great introduction to ORRNs and their challenges, many experiments and a thorough appendix with many implementation details for reproducibility
summary: This paper introduces Quantized Orthogonal Recurrent Neural Networks (QORNNs) to address the memory and computational limitations of traditional Orthogonal Recurrent Neural Networks (ORNNs) on compact devices. While ORNNs are valued for their capability to handle long-term dependencies in tasks like the copy-task, their reliance on full-precision weights makes them unsuitable for deployment in resource-constrained environments. The authors propose two methods for quantizing ORNNs: Quantization-Aware Training (QAT) with orthogonal projections and post-training quantization for activations, ensuring both efficiency and stability in the recurrent weight matrices. These methods allow QORNNs to maintain the benefits of orthogonality while using fewer bits for weight representation.
weaknesses: There is unfortunately not any real innovation in the paper. The only contribution of the paper is applying QAT with a straight-through estimator (a very old idea in quantization literature) to existing optimization methods for learning ORNNs. In fact, the QAT technique is not even state-of-the-art as they could learn the quantization ranges $\alpha$ through gradient by adopting LSQ$^{[1]}$ or PACT^{[2]}. 

The theoretical analysis of the impact of quantization in orthogonal matrices is not optimal. It is well known that using MinMax quantization for low-bit quantization (< 6 bits) leads to significant degradation. This is why search-based methods are normally adopted that find the scale or range that minimizes the Forbenious ( or other norms) between quantized and unquantized vectors (commonly known as MSE-based ranges). It would be more interesting to see the plots of Figures 1 & 2 using optimal $\alpha$ values rather than ones based on the maximum range. 

[1] LSQ: Learned Step Size Quantization, Esser et al. 
[2] PACT: Parameterized Clipping Activation for Quantized Neural Networks

Meta-review: There were serious concerns raised by the reviewers related to the lack of novelty, poor writing, and experimental evaluations. 

The authors did not reply to those concerns during the rebuttal period. Since the paper did not receive promising reviews to begin with and the authors did not reply to the concerns raised, I am proceeding with the judgement of the reviewers and suggesting rejection of this work in its current form.

Decision: Reject