HADAMRNN: BINARY AND SPARSE TERNARY ORTHOGONAL RNNS
Authors: Armand Foucault
Francois Malgouyres
Franck Mamalet
Venue: ICLR 2025 Poster (2025)
Keywords: Recurrent neural networks
quantization
orthogonal matrices
Hadamard matrices
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: This paper proposes a novel method to binarize the recurrent weight matrix of an orthogonal recurrent neural network. It also proposes a method to make the recurrent weight matrix sparse and ternary.

Abstract: Binary and sparse ternary weights in neural networks enable faster computations and lighter representations, facilitating their use on edge devices with limited computational power. Meanwhile, vanilla RNNs are highly sensitive to changes in their recurrent weights, making the binarization and ternarization of these weights inherently challenging. To date, no method has successfully achieved binarization
or ternarization of vanilla RNN weights. We present a new approach leveraging the properties of Hadamard matrices to parameterize a subset of binary and sparse ternary orthogonal matrices. This method enables the training of orthogonal RNNs (ORNNs) with binary and sparse ternary recurrent weights, effectively creating a specific class of binary and sparse ternary vanilla RNNs. The resulting ORNNs, called HadamRNN and Block-HadamRNN, are evaluated on benchmarks such as the copy task, permuted and sequential MNIST tasks, and IMDB dataset. Despite binarization or sparse ternarization, these RNNs maintain performance levels comparable to state-of-the-art full-precision models, highlighting the effectiveness of our approach. Notably, our approach is the first solution with binary recurrent weights capable of tackling the copy task over 1000 timesteps.

Published conference paper at ICLR 2025
HADAMRNN: BINARY AND SPARSE TERNARY ORTHOG- ONAL RNNS
Armand Foucault
Franck Mamalet Institut de Recherche Technologique Saint Exupéry Toulouse, France franck www.meeeeerrtteeeeeeeeeeeeeeeeee
Institut de Mathématiques de Toulouse, UMR5219. Université de Toulouse, CNRS. UPS IMT, F-31062 Toulouse Cedex 9, France armand. foucault @math. univ-toulouse.
François Malgouyres
Institut de Mathématiques de Toulouse, UMR5219. Université Toulouse, CNRS. UPS IMT,
F-31062 Toulouse Cedex 9, France
francois mow eeatheemmmhh....e.e.mm...arraare www.:tth..iiiiotuuiu www.-tuuuuusue............ oo fr
ABSTRACT
Binary and sparse ternary weights in neural networks enable faster computations and lighter representations, facilitating their use on edge devices with limited computational power. Mcanwhile, vanilla RNNs highly sensitive to changes in their recurrent weights, making the binarization and ternarization these weights inherently challenging. To date, method has successfully achieved binarization or ternarization vanilla RNN weights. We present new approach leveraging the properties of Hadamard matrices parameterize subset of binary and sparse ternary orthogonal matrices. This method enables the training of orthogonal RNNs (ORNNs) with binary and sparse ternary recurrent weights, effectively creating a specific class of binary and sparse ternary vanilla RNNs. The resulting ORNNs, are evaluated on various benchmarks,
named HadamRNN and Block-HadamRee including the copy task, permuted and sequential MNIST tasks, the IMDB dataset, two GLUE benchmarks, and two loT benchmarks. Despite binarization or sparse ternarization, these RNNs maintain performance levels comparable to state-of-the- art full-pree full-precision models, highlighting the effectiveness of our approach. Notably, approach is the first solution with binary recurrent weights capable of tackling the copy task over 1000 timesteps.
INTRODUCTION
A Recurrent Neural Network (RNN) is neural network architecture relying recurrent putation mechanism at its core. These networks are well-suited for the processing of time series, thanks to their ability to model temporal dependencies within data sequences. Traditional Recurrent architectures such as vanilla RNNs, LSTM (Hochreiter and Schmidhuber 1997). GRU (Cho et al. 2014) or Unitary/Orthogonal RNN (Arjovsky et al. 2016)] Helfrich et al.) 2018) have achieved remarkable performance across various sequential tasks including neural machine translation (Devlin ct al. 2014, Sutskever et al., 2014) and speech recognition (Amodei et al. 2016 Chan al. 2016).
Modern RNN architectures typically rely millions, or even billions, of parameters to perform optimally. This necessitates substantial storage space and costly matrix-vector products at inference- time, that may result in computational delays. These features can be prohibitive when applications must operate in real-time or on edge devices with limited computational resources.
A compelling strategy to alleviate this problem is to replace the full-precision weights within the network with weights having low-bit representation. This strategy, known as neural network quantization (Courbariaux et al. 2015; Lin et al. 2015) Courbariaux et al. 2016 Hubara et al.) 2017] [Zhou et al., 2016), has been extensively studied over the recent years. For optimal computational efficiency and memory savings, weights should be binarized, that is, represented over only bit. For

---

Published conference paper at ICLR 2025
the case of recurrent networks, it was shown (Ott et al. 2016 He al. 2016 Hou al.
2017 Alom
et al. 2018 Ardakani et al., 2019) that LSTMss and GRUs with binarized weights could achieve near state-of-the-art results on natural language datasets such as Penn TreeBank (Marcus et al. Tolstoy's War and Peace, (Hou et al. 2017 or IMDB (Maas et al., 2011).
1993). Leo
However, vanilla RNNs, LSTMs and GRUs usually struggle at learning tasks involving very long-term dependencies, notably due to the exploding gradient problem (Pascanu et al. 2013). In Arjovsky ct al. (2016); Wisdom et al. (216)); Cezzano-Casadee et al. 2019) for instance, it can be observed that LSTMs fail to solve the copy task with long sequences. In recent years, alternative models including transformers /Vaswani et al., 2017), ODE-inspired RNNs (Erichson et al. 202T; Rusch and Mishra 2021) including SSMs (Gu et al. 2022 were designed accurately model long- dependencies. Among these, recent studies have tackled the challenge of quantizing transformers, but have only achieved model sizes in the tens of megabytes (see Section and Appendix F.I). The only known attempt to quantize SSMs reports significant loss of accuracy when reducing precision below 8-bit (Abreu et al. 2024). Hence the need for efficient, lightweight, binary recurrent architectures capable of handling longer dependencies than LSTMs and GRUs.
Contribution: In this paper. we binarize the recurrent weights of Orthogonal Recurrent Neural Networks (ORNNs), which is a special case of vanilla RNNs. The binary orthogonal matrices are constructed using Hadamard matrix theory. We call these networks Hadamard RNNs (HadamRNN). To the best of our knowledge, this is the first successful attempt to binarize the weights of vanilla and orthogonal RNNs. To reduce the complexity further, we also build sparse ternary ORNNs called RNNs Hadam-NHadmRNNN, The resulting HadamRNNs and Block-HadamRNNy are fully- qullty-uaazzzddd lightweight. highly efficient, and model long-term term dependencies more accurately than LSTMs and GRUs This claim is supported by results copy task for 1000 timesteps, permuted MNIST, pixel-by-pixel MNIST, the IMDB dataset, two GLUE benchmarks, and two IoT benchmarks. Despite the drastic reduction in computational complexity and memory footprint, the performance degradation remains moderate compared to full-precision ORNNS. Ablation studies show the effectiveness of the choices made in the article.
variety of benchmarks including the
Organization of the paper In Section 2 we review previous work on binarizing and ternarizing the weights of neural networks for sequential data modeling. The bibliography supplemented by Appendix [A] which focuses on ORNNs. In Section 33 we describe the method for parameterizing a subset of binary and sparse ternary orthogonal matrices. We also outline all the components of Experiments are detailed in Section 4 and conclusions are
HadamRNNs and Block-HadamRRNg
provided in Section 55)
Additional bibliographic references are in Appendix A and proofs are provided in Appendix B Appendix Cillustrates the model description. Details for reproducing the experiments, along with additional experimental results, are in Appendix D Appendix D and Appendix D Theoretical
complements and an ablation study on the (linear) ORNN architecture are in Appendix G while those on the proposed parameterization of orthogonal matrices are in Appendix H The fixed-point arithmetic implementation is detailed in Appendix !
The code implementing the experiments is available hadamRNN
RELATED WORKS
This section provides an overview of prior research efforts aimed at quantizing the weights of neural networks designed for handling sequential data, encompassing both recurrent and non-recurrent architectures. We first highlight the works that report performance with binary and ternary recurrent weights. Further bibliographical details on ORNNs can be found in Appendix
In the seminal paper Out et al. (2016), the authors apply binarization and ternarization methods on vanilla RNN, LSTM and GRU architectures. Remarkably, they acknowledge the difficulty of training binary RNNs; they write at the beginning of Section 1.1. 'We have observed among all the three RNN architectures that BinaryConnect on the recurrent weights never worked. In Hou al. (2017), the authors apply a loss-aware binarization scheme to an LSTM and achieve better performances than the conventional BinaryConnect algorithm (Courbariaux et al. 2015) on a language modeling task. Using a learning process incorporating stochasticity and maacch-ormalization Ardakani et al. (2019) show that L.TT and GRU with binary weights can achieve results comparable to their
2

---

Published conference paper at ICLR 2025
full-precision counterparts on language modeling tasks and the sequential MNIST task. Finally, He et al. (20T6); Liu et al. (2018); Wang et al. (2018); Alom et al. (2018) take step further toward fully quantized recurrent network. He et al. 2016) proposes to quantize the activations of a GRU and an LSTM in addition to binary weights. Liu et al. (2018) suggests to binarize the word embeddings as inputs for an LSTM with binary weights, Alom et al. (2018) propose another quantization scheme and implement quantized convolutional LSTM which are tested on the moving MNIST dataset.
Among the articles cited above, Ott et al. (016); Hou et al. (207): ;; Ardakani et al. (2019); He et al.
(2016) consider character-level language models. The works by Ardakani et al. 20199; Wang et al.
(2018); Liu et al. (2018) report performance results for word-level language models. He et al. (2016);
Alom et al. (2118) address sentiment analysis on the IMDB dataset (Maas et al. (011). Ardakani et al. (2019) is the only article reporting results for a long-term dependency problem, that LST'M are known to solve efficiently: the sequential MNIST problem. Kusupati al. (2018) is the only work to solve IoTT tasks. None of the articles attempts to solve the permuted MNIST problem or the copy task for 1000 timesteps, both of which are known to be better addressed by ORNNs.
Quantization methods for LSTMs and GRUs using larger bit-widths have been described in Hubara al. (2017); Kusupati et al. (2018) Nia et al. (2023); Xu et al. (2018): Zhou et al. (2017).
To the best of our knowledge, the only article describing a method for quantizing ORNNs is Foucault jtt al. (022).. In this article, the authors succeed in learning tasks involving long-term dependency
with bit ORNN.
We classify existing efforts to quantize Transformers such as BERT (Devlin 2018) based on the level of quantization applied. Some approaches focus on quantizing the weights to 8 bits ZZffrir al. 2019 (Sun et al.] 2020; (tock et al. 202T) or even 4 bits (Shen al. 2020 Zadeh et al. 2020p. Others explore more aggressive quantization, employing ternary weights (Zhang et al. (020) or binary weights (Bai et al.
2021). Fully binarized versions of BERT, including binarized activations,
presented in (Qin et al.
2022 Liu et al. 2022).
As shown in Appendix F.T Table 6 all these networks require at least tens of megabytes of storage. This contrasts sharply with the models described in this article, which require much smaller sizes.
Finally, Yao et al. p022]; Frantar et al. (203)); Xiao et al. (2023); Liu et al. (202)) extend quantization techniques to large language models with billions of parameters.
3 HADAMARD AND BLOCK-HADAMARE RNNS
We describe the details of the considered ORNNs in Section 3.1 A brief review of the key properties of Hadamard matrices is provided in Section 3.2 matrices are used to build ORNNs with binary recurrent weights that we call HadamRNN. We extend the construction to sparse ternary recurrent weight matrices, referred to as Mlock-HadamRNN, in Section 3.4 We describe how input and output weight matrices are quantized in Section 3.5 and compare the complexities of the proposed models Section 3.6
We explain, in Section 3.3. how Hadamard
3.1 ORNNS
Orthogonal recurrent networks class of recurrent networks that rely on the same recurrent operation as the one of a vanilla recurrent network, but add an orthogonality constraint on the recurrent weight matrix. Given sequence of inputs xj...., Rdd., the model computes sequence of hidden states hp.....h, hy &d according to
h, W h,- Ux,+
where hg = 0, a matrix U E Rd,xd,,, b, E Rdh, and the recurrent weight matrix W E Rd,xd, is constrained to be orthogonal (i.e. W'W WW' Idp where W' is the transpose of W. and Id, is the identity matrix of size d, x dz,). Depending on the task, the output is either the vector Vo(h, + bb E Ra or the time series Va(h,) + b..., vo(h,) + b,- The matrix V E Rd is the output matrix, and is the activation function.
The orthogonality of the recurrent weight matrix enhances memorization and prevents gradient vanishing. These networks have been shown to solve complex tasks with long-term dependencies,
3

---

Published conference paper at ICLR 2025
such as the copy task with 1000 timesteps or more ezzanooCasado al. (2019): Helfrich al.) (2018); Vorontsov et al. 2017); MMammedi et al. (0017). They also lead to simple RNNs, whose inference complexity scales linearly with sequence length.
The most common choice in ORNNS is to apply the ReLU activation function, to each hidden state update. The formula then becomes h = a + UXx + b,), and the output is simply Vhy b.. In D. we consider ORNNs with linear recurrent units. The use of the linear recurrent unit improves memorization (see Appendix G) and is also motivated by studies on SSMs (Gu et al. 2022
Orvieto
et al. 2023). We provide an ablation study to support this choice in Appendix G.1
3.2
INTRODUCTION TO HADAMARD MATRICES THEORY
Before describing how we construct binary or sparse ternary recurrent weight matrices in Sections 3.3 and 3.4 we first recall known properties of Hadamard matrices (Hedayat and Wallis 1978), and explain how, under simple conditions, we can parameterize a subset of all Hadamard matrices.
Definition 3.1. Hadamard matrices (Hadamard 1893) are square matrices with binary values in (-1, IJ. whose rows are pairwise orthogonal. For any n E N*, we denote by H, the (possibly empty) set of all Hadamard matrices of size X n.
Notice that for any > 1 and any Hadamard matrix W of size X n, we have
WW = nl
(2)
is well known that for n > 2. Hadamard matrices of size n X n do not exist unless n is a multiple
of 4 (Hedayat and Wallis 1978). The existence of Hadamard matrices of size 4n 4n for all n remains conjecture. It is called the Hadamard conjecture (De Launey and Gordon 2001). It is
therefore hopeless to attempt learning an optimal matrix in H, for an arbitrary n.
The following proposition outlines straightforward method, introduced in Sylvester 1867). to
construct a Hadamard matrix of size 2 x 2 for any k 2
Proposition 3.2. Let k 2 1. The 2 x 2* matrix, denoted Syt, defined recursively by
/Sa-11
S24-1
S² 5 1) (i.e. if 1), and Sze
, if > 1,
S
Spe-1
is a Hadamard matrix. It is called the Sylvester matri of size 2 (Horadam 2007
The proof is provided for completeness in Appendix B.2
For any 1, if Hadamard matrix of size X is known, the following proposition provides a simple method for generating 2" distinct Hadamard matrices. In the proposition, the notation diag(u) IR refers diagonal matrix with E R" on its diagonal.
Proposition 3.3. For 1 and any H E Hg the mapping
4H 1-1,1)" [-1.1)
u Hiag(u)
injective. Moreover, for all E 1)", Φ (u) is a Hadamard matrix.
The proof is provided for completeness in Appendix B.3 This proposition guarantees that switching the signs of any set of rows of a Hadamarad matrix preserves its Hadamard property. Considering the matrices Φs,, (u), for u E (-1,1) Proposition 3.2 and Proposition 3.3 provide method for
manipulating 2n Hadamard matrices of size 2* x 2* for k 2 1. For instance, when d, = 2 = 256, this allows the generation of more than 10?? different matrices. The experiments will confirm that this class of matrices possesses sufficient expressiveness.
Note that even if, in the following, we only use Proposition 3.3 with Sylvester matrices whose size is power of 2, Proposition 3.3 applies to any given Hadamard matrix H. Many such matrices exist.
These matrices also called Walsh matrices in some contexts.
4

---

Published conference paper at ICLR 2025
In particular, Hadamard matrices can be constructed for almost all sizes 4n x 4n, when 4n I 2000 (Doković et al. 2014). This would allow parameter d, to be set more finely than we have done.
key point is that, due to the independence of u's components, empirical results show that can be optimized using standard methods like the straight-through estimator (STE) (Hinton 2012 Courbariaux al., 2016), as described in Appendix
Finally, similarly to what has been done in Proposition 3.3 it can also be shown that it is possible to switch the signs of any set of columns Hadamard matrix and preserve the Hadamard property. We argue in Appendix H.1 that, because also optimize the imput matrix U and the input bias b does not lead more expressive networks. Additionally, the ablation study in Appendix H.2 shows that it does not allow for any improvement in practice.
3.3 BINARY ORTHOGONAL RECURRENT WEIGHT MATRICES
To parameterize the binary orthogonal recurrent weights used in our network, reffered to as Hadamard RNN (HadamRNN), we consider d,, 2* for and the weights
(w))
diag(u) Szz Rdxxd, vd
for a trainable binary vector 111, Indeed, using that diag(u) Sz is Hadamard matrix satisfying 2 we obtain that (u) is orthogonal: Www'WWu)) = W Wu))W()) = dd. The proof is provided in Appendix B.4 We also detail an example in Appendix C It is worth noting that if k is even, d, = 2 for K N 1, then the normalization becomes a division by Vd, 2 which is well-suited for efficient implementation on edge devices.
3.4 SPARSE TERNARY ORTHOGONAL RECURRENT WEIGHT MATRICES
To construct the sparse ternary orthogonal recurrent weights used in HadamRNNs), we consider d, = 42%, where k 2 and 2 1, with the weights defined as
RNNs (Block-
(u) = diag(u) (1, @ Szx) E R4xx,,
24
for a trainable binary vector E (-1, 11th and the Kronecker product @ (see Appendix 1). The matrix (u) is ternary since its components are reasons outlined in the previous section. The proof is detailed in Appendix B.4
It is orthogonal for the same
V2F"
2
The proportion of non-zero components in (u) is g(5522 = 1. When is large, the matrix (()) 4
19207
very sparse. On the contrary, when g 1, none of the components of W(u) is zero, and the Block- Hadamard RNN effectively becomes Hadamard RNN as described in the previous section. In this sense, Hadkm-add RNNs are natural sparse ternary extension of Hadamard RNNs.
3.5 MATRICES U AND V QUANTIZATION
Because input and output sizes are often much smaller than the size of the hidden space (i.e. dmn < dp and d & dz), we permit the quantization of the input and output weight matrices, and V. using p bits, where 2 2. We use the uniform quantization with scaling parameter (Gholami et al. 2022).
The quantization approximates every component of U (resp. V) by its nearest element the set
---1 2- 12111111-- 1
II
where max,y | (resp. max,, Ilyl) and the set Ja, b] contains all the integers between and b. The above set contains 2n elements.
To obtain temary U and V. leading to matrix-vector multiplications involving only additions, also provide the results for the quantization approximating each component of U (resp V) in a 11,, 0, 1). for the same values of a.
5

---

Published conference paper at ICLR 2025
Moreover, when the input one-hot encoded, only one column of U is used at time. The product Ux, can take only din values and, from computational perspective, can be encoded as the input bias b, and the activation.
3.6 MODEL SIZE AND COMPUTATIONAL COMPLEXITY
We compare the different models in terms of parameter storage requirements and the number of operations during inference.
The model size is determined by the total number of learnable parameters, multiplied by the number of bits used to encode each parameter. In both HadamRNNs and Block-Hadane Block-HadmRRNNs, the recurrent layer requires d, bits for encoding the binary vector u, the input matrix requires d bits, and
d,(++(d,,
the output matrix V requires d oP bits. Therefore, the total model size is given by 8x1024
kByte It is important to note that using Sylvester matrices S2e eliminates the need to store their weights, as these can be easily retrieved using Proposition 3.2
The number of operations of the inference using HadamRNN and Block- HadamRNN is detailed in Table We assume Table [ that the hidden and input variables, h; and x,, are encoded using Po bits. A detailed description of the fully quantized RNN operations is given in Appendix [ HadamRNNs and Hadamsss use binary (or ternary) recurrent matrices, which eliminates the need for multiplications. Similarly, for ternary U and V. we set pppp.p' 0 since the matrix-vector multiplications only involve additions. When = 2. the matrix- multiplications involving matrices U and V in (-2, 0, 1] only involve additions and bit-shifts. For the same d value (d,, 2 9.2% with k' < k). the computational complexity of the recurrent layer of Block- HadamRNN is q times lower than that of HadamRNN.
For comparison, also provide the complexity for the inference with full-precision ORNN (Arjovsky et al. 2016) and the only quantized ORNN that we are aware of: QORNN (Foucault et al. 2024). The complexities of HadamRNN and Block-HadamRNe are much smaller, in particular, because, as will be reported in Section 4 they permit achieve satisfactory results for p = 2 when, reported Foucault et al. (2024), QORNNS require least p = bits encoding.
Note that when the inputs x, are one-hot encoded, computing Ux, requires no multiplications and only d, additions. This further reduces the complexity compared to Table
Table I: Computational complexity for an inference of the RNN. We neglect the bit-shifts and the accesses to the look-up tables. FP stands for in floating-point arithmetic, fpp stands fixed-point precision additions, fppp... stands for fixed-point precision multiplications between numbers coded using p and Pa bits. We have fppr.p. fpp2.. = O, where fprr.p is for ternary matrices.
Layer
Operation
ORNN
QORNN
HadamRNN dn = 2k idem idem
Block Boock-HadmRRNN
dn 92
Input
Mult. Add.
dn FP
dm fpPp.s dn fpp
idem
dn FP
idem
Recurrent
Mult. Add.
dn.dn FP
dn fpPmes dn fpp
dn.dn FP
dn.dn fpp
dn de fpp
Output
Mult.
dp.4am our
FP
dn fpPp.. d fpp
idem
idem
Add.
d das FP
idem idem
EXPERIMENTS
In this section, we assess the performance of HadamRNN and Block-Hadamll on four standard benchmark datasets. These datasets are described in Section 4.1 Three tasks require retaining
"The biases b, and (d, d,)p, bits.

---

Published conference paper at ICLR 2025
information over extended periods, while the fourth focuses on a Natural Language Processing (NLP) task with shorter sequences but larger input dimensions. In Section 4.2 we present the performance of HadamRNN and Madkk-Ha and compare them to that of previously published quantized and full-precision (FP) models. We conduct ablation studies in Appendix G.1 and Appendix H.2
4.1 DATASETS
We investigate lightweight neural networks for time series and select datasets suited to these archi- tectures. In particular, this excludes the Long Range Arena benchmarks (Tay et al. 2020), which are too complex for full-precision ORNNs, LSTMs, and GRUs. To illustrate the limitations of the proposed models, we include the sequential MNIST for which LSTMs are known to outperform ORNNS. Copy task The Copy task is a standard sequential problem first introduced
(Hochreiter and Schmidhuber 1997). This task requires memorizing information over many timesteps, and vanilla LSTMs are notoriously unable to solve for long sequences (Arjovsky et al. [0166] Helfrich ct al.
2018 Lezcano-Casade et al. 2019). We follow the setup of Lezcano-Casado et al. (2019).
in which the data sequences are constructed as follows. We consider an alphabet {ax k of 10 characters. Given sentence length K and a delay I., the first K elements of an input sequence
sampled uniformly and independently from {ax ) k=1' These are followed by L repetitions of the blank character 4g. one instance of the marker ag. and K - repetitions of 40- The first K elements form sentence that the network must memorize and reproduce identically after outputting L. + K instances of ag-
In our experiments, we fixed K 10 and L 1000 (7 L +K 1020, dn 10, dour 9). The loss function is the cross-entropy, which is also used to measure performance. A naive baseline consists of K repetitions of ag. followed by K random values. This leads to a baseline cross-
entropy of l0 = 0.021.
L+2K
Permuted and sequential pixel-by-pixel MNIST (PMNIST/SMNIST) They are also classic long- term memory tasks. From the MNIST dataset, the 28 x 28 images are serialized into 784-long sequences of 1-dimensional 8-bits pixel values (T = 784, d 1, dour = 10). The serialization is done pixel-by-pixel for sMNIST. For PMNIST, a fixed permutation used to shuffle the pixels within each sequence. We apply the same permutation as Kiani et al. (2022). The task is to predict the correct handwritten digit label at the last step. The learning loss is the cross-entropy. and the model's performance is evaluated with accuracy.
IMDB This dataset, proposed in Maas et al. (201I), I), is an NLP binary classification task for sentiment analysis based on 50,000 movie reviews. As in He al. (206)), pad and cut the sentences 500 words, and use a learnable word embedding vector of size 512 (T = 500, d., = =512, d = 1). The learning loss is the binary cross-entropy, and the model's performance evaluated with accuracy.
Other Datasets We provide in Appendix ala comparison of HadamRNN, Block-HadamRR HadammNN,, and transformers the SST-2 and QQP benchmarks from GLUE (Wang et al. 2019), as well with RNNs on IoT task benchmarks: HAR-2, and DSA-19, as described in Kusupati et al. (2018)
4.2 PERFORMANCE EVALUATION
The evaluation is organized follows. In Section 4.2. and Table 2 we compare the results of HadamRNN to those of the state-of-the-are In Section 4.2.2 and Table we compare the results of and HadamRNN.
Block-Hadamle
For each task, hyperparameters were selected using validation sets, and final performance was evalu- ated on test sets. Details on the hyperparameters and implementations are provided in Appendix D
Training times are provided in Appendix H.1 Training stability is analyzed in Appendix E.2
4.2.1 HADAMRNN VERSUS THE STATE-OF-THE-ART
Since aim to design regh-performacc RNN architectures adapted to low-memory devices, assess the models' performance based on two criteria: the model size of each architecture and its classification accuracy or cross-entropy for the copy task. The model size of HadamRNN is calculated
7

---

Published conference paper at ICLR 2025
as described in Section 3.6 LSTM recurrent matrix the identity matrix and is coded using 0 bits. We also report the performance of fully quantized HadamRNN using the post-training quantization strategy for activations detailed in Appendix[I !| The main performance results on the four benchmark datasets are summarized in Table 2 The plots in Appendix E..3 based the results from Table 2
highlight the efficiency of HadamRN NNN in terms of model size.
State-of-the-ars We compare HadamRNN with state-of-the-art full-precision and quantized models designed for time series modeling:
Full-precision LSTM (Jing al., 2017 Kiani et al. 2022) and quantized LSTM (Ardakani et al., 2019 Alom et al. 2018: He et al. 2016) are known to fail the 1000-timesteps Copy task, and to be well-suited for modeling the sMNIST problem. LSTM also serves as an optimistic proxy for other gated models such as GRU, since LSTM is known to usually
perform better.
Similarly to HadamRNN, ORNN (Kiani et al. 2022) and QORNN (Foucault et al. 2024) are instances RNNs with orthogonal recurrent weight matrix. but operating with different bitwidth. This comparison evaluates the performance degradation caused by binarization.
FastGRNN (Kusupati et al.) 2018 was designed to address similar problems as unitary RNNs (Arjovsky et al. 2016 Helfrich et al. (2018) but with significantly smaller size. Since HadamRNN is also remarkably lightweight, it appears relevant to compare the two models.
As stated in Section [ quantized SSMs perform poorly when the bitwidth is smaller than 8 bits (Abreu et al. 2024). Also, as discussed in Section 2 and Appendix [..T the differences in size and complexity between transformers and HadamRNN render the comparison meaningless. For these reasons, we do not include the results of transformers and SSMs.
Copy-task Notably, HadamRNN is the first binary recurrent weights solution capable of learning the long-term dependency of the Copy task. Note that full-precision and quantized I.S LSTTM do not learn the Copy task when T 1020. The proposed HadamRNN outperforms the 5-bits QORNN introduced in Foucault et al. 22224, while requiring a smaller recurrent size d,. The resulting model size reduction is over 36 (= 50.6/1.44 1.40). This improvement stems from the orthogonal nature of the Hadamard matrices, which enables better learning of long-term dependencies compared to QORNNs, where the matrices are only approximately orthogonal. This is also attributed to the choice of a linear recurrent unit, which enhances memorization (see Appendix G
PMNIST Similarly, on PMNIST, the fully quantized HadamRNN, with a size of just 3.58 kB, outperforms the QORNN of Foucault et al. (2024), which requires 35 kB, and even full-precision ORNN of 120 kB. Additionally, the HadamRNN model of 6.2 kB achieves only 1.2% lower accuracy compared to an ORNN with d, = 512 of much larger size, 1046 kB. All HadamRNN architectures, except for the smallest one, outperform full- full-precision LSTMs.
sMNIST For this task, which typically favors gated models like LSTM and FastGRNN, the Hadam- RNN model of size 3.58kB achieves an accuracy that is only 2% lower compared to LSTMs and FastGRNNN of the same size, and full-precision ORNN of size 1046kB. It still outperforms the QORNN, achieving 96.9% accuracy with a model size that is 5.6 (= 35/ /6.22) times smaller.
IMDB The smallest HadamRNN models with d, 128 outperform Alom et al. (018) binary LSTM, while being 2.4 (=
times smaller, and when increased to d, = 512 with a size of 129 kB, it achieves 10% higher accuracy compared the 40.5 kB model. It also outperforms the full precision ORNN with d,, 128. The b-bi (resp. b-iis)) LSTM proposed in He et al. (2016) only offers 1% accuracy advantage over HadamRNN at the same recurrent size d 512 but their model size is 4 (resp. 8) times larger.
Activation quantization Regardless of the task, the results of Table 2 demonstrate that post-training quantization of activations, as described in Appendix [I does not degrade performance.
4.2.2
VERSUS HADAMRNN
When Haac-aaa and HadamRNN share the same hidden-spare dimension, they have equal size. Their main difference lies in the computational complexity of their recurrent unit, which, as explained in Section Table is q times lower for Elock-HadamRNA In Table we therefore report the computational complexity and the performance for the four considered tasks.
8

---

Published conference paper at ICLR 2025
Table Comparison HadamRNN and the state-of-the-art on several benchmark datasets, Last column reports the model size in kBytes. BL (baseline) means that the model failed to learn.
Model
dn
W
U & V bitwidth
activation bitwidth
performance
size
bitwidth
kBytes
Copy task (7 = 1000, d,. = 10, d = 9, cross-ent, baseline 0.021)
LSTM Jing al. (2017)
FP
FP
FP
BL
112
ORNN (Kiami ct al. (022))
256
FP
FP
FP
1.1c-12
275
QORNN (Foucault et al.
22024
8
8
12
1.7c-5
75.5
QORNN Fouccuul
2024
5
12
2.Se-3
50.6
FP
BL
1.44
FP
1.6e-7
1.74
HadamRNN (ours)
128
4
12
2.3e-7
1.40
6
FP
3.2c-8
2.33
Permuted MNIST (T = 784. d,,
d
10, accuracy)
ORNN
Kiani ct al.
2022
512
FP
FP
FP
97.00
1046.0
ORNN
Kian
2022
170
FP
FP
FP
94.30
120.2
LSTM
Kiani et
2022
FP
FP
FP
92.00
456.9
QORNN
Foucault
al
94.76
35.0
QORNN
Foucault et al.
20244)
6
12
93,94
27.9
2
FP
91.13
3.48
4
FP
94.88
4,85
HadamRNN (ours)
512
12
94.90
3.58
FP
95.85
6.23
Sequential MNIST (T 784, d
1, 1,
10, accuracy)
LSTM (Ardakani al. 2019))
100
0
1
12
98.6
5.11
FastGRNNN (Kusupati
(018))
170
16
98.2
6.0
ORNN (Leccano-Casaal
02.19
FP
FP
98.7
1046
QORNN
Foucault el al. 2024
170
8
8
12
96,2
35.0
QORNN
(oucault et al. 2024
170
6
6
12
94.74
27.9
FP
92.65
3.48
FP
96.63
4.85
HadamRNN (ours)
512
12
96.34
3.58
6
FP
96.9
6.23
IMDB (T' = 500, d,, 512, d
I, accuracy)
LSTM
Alom et al. 2018
FP
76.25
40.50
LSTM
Alom et al 2018
128
2
FP
79.64
80.5
0
LSTM
He et al. 2016))
512
2
2
88.12
514
LSTM
He ct
2010
512
4
4
88.48
1026
ORNN
128
FP
FP
FP
84.02
320.5
ternary
HP
81.18
16.55
128
2
FP
85.34
16.55
HadamRNN (ours)
2
12
85.18
16.24
FP
87.43
130.32
512
87.13
129.06
For a given size d,, reducing improves performance. On the contrary. increasing improves computational complexity. For instance, Block-Hadanil with q = consistently solves the copy task with only 2048 fixed-poin precision additions. compared to the 16. 384 ones required by HadamRNN, addition, for the copy-task and sMNIST, Mlock-HadamRNg with = 2 has negligible drop of accuracy compared to HadamRNN, while calculating product with its recurrent weight matrix requires only half the number of fixed- soint precision additions. This, along with the plots in Appendix E.3 based the results from Table demonstrates that Block-Hadamin facilitates exploration the trade-off between computational complexity and performance, offering flexible control over both performance and resource utilization.

---

Published conference paper at ICLR 2025
Table Comparison of the performances Block-HadamRNN (with paramer q) and HadamRNN (q = 1) on several benchmarks. The last column reports the computational complexity of the recurrent operation W h, measured in fixed- peed-piint precision additions (see Table TT. The quantization bitwith of matrices U and V is 4 and the activations are not quantized.
Model
dn
W
parameter q performance
computational complexity
bitwidth
in
Copy task (7 = 1000, 4n = 10, a = 9, cross-ent, baseline 0.021)
32
1. 1.6e-3
512
Bock-HHadmRNN
128
ternary
8
6.6e-5
2048
2
2.0c-6
8192
HadamRNN
128
1.6e-7
16,384
Permuted MNIST (T 784, d
dour 10, accuracy)
128
60.74
2048
32
91.42
8192
Block-HaNamRNNN
512
ternary
8
91.45
32,768
2
93.12
131,072
HadamRNN
512
94.88
262,144
Sequential MNIST (T 784, d = 1, d our = 10, accuracy)
128
27.45
2048
32
80.60
8192
Bookk-HadmRNNN
512
ternary
8
92.49
32,768
2
96.47
131,072
HadamRNN
512
96.63
262,144
IMDB 500, d 512, d 1, accuracy)
128
81.83
2048
32
84.27
8192
Block-Ha
512
ternary
8
85.70
32,768
2
86.30
131,072
HadamRNN
312
87.43
262,144
5 CONCLUSION
Drawing on Hadamard matrix theory, this article presents a method for parameterizing a subset of binary and sparse ternary orthogonal matrices. We demonstrate that the parameters of such matrices can be learned using standard methods like the trriight-through estimator (STE), and empirically validate that this subset is sufficiently expressive to solve standard RNN benchmarks. This work is the first to construct efficient orthogonal RNNs with binary and sparse ternary recurrent weight matrices. This recognized
challenging problem by Out al. (016)) and has been addressed since. Experimental results show that the proposed HadamRNN matches the performance of floating- ORNNs while reducing the model size by up to 290-fold. Notably, is the first binary recurrent weight model capable of learning the copy task with more than 1,000 timesteps. With the proposed sparse- ternary models, Block- HadamRRN,,, we offer ways fine-tune the balance between performance and computational efficiency. Future work could explore the following directions: (1) binarizing or ternarizing Structured State Space Models to address tasks with even longer-range dependencies, such as those in the Long Range Arena benchmark (Tay et al. 2020); (2) deploying HadamR on edge devices; and (3) applying binary orthogonal matrices to other domains, including time series forecasting (Wu et al. 2021] Zhou et al. [202] (022), neural network robustness (Cisse et al.)
2017] Anil et al. 2019). Normalizing Flows (Kingma and Dhariwal 2018), and Wasserstein distance
estimation (Brock al. 2018).
10

---

Published conference paper at ICLR 2025
ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
This work has benefited from the AI Interdisciplinaryy Institute ANITI, which is funded by the French "Investing for the Future PIA3" program under the Grant agreement ANR-19-PSIA-0004 The authors gratefully acknowledge the support of the DEEL project P A. Foucault was supported by "Région Occitanie, France', which provided a PhD grant. Part of this work was performed using HPC resources from CALMIP (Grant 2024-P22034).
REFERENCES
Abreu, E. Pedersen, M. Heckel, and A. Pierro. Q-s5: Towards quantized state space models. arXiv preprint S011:2240600947777 2024.
M. Z. Alom, A. Moody, N. Maruyama, B. C. V. Essen, and T. M. Taha. Effective quantization ap- proaches for recurrent neural networks. 2018 International Joint Conference on Neural Networks (JCNNN, pages 1-8, 2018.
D. Amodei, S. Ananthanarayanan, R. Anubhai, J. Bai, E. Battenberg, C. Case, J. Casper, B. Catanzaro, Q. Cheng, G. Chen, et al. Deep speech 2: End-to-end speech recognition in english and mandarin. In International Conference on Machine Learning, pages 173-182. PMLR, 2016.
C. Anil, J. Lucas, and R. Grosse. Sorting out lipschitz function approximation. In International Conference on Machine Learning, pages 291-301. PMLR, 2019.
A. Ardakani, Z. Ji, S. C. Smithson, B. H. Meyer, and W. J. Gross. Learning recurrent binary/ternary weights. In International Conference on Learning Representations, 2019.
M. Arjovsky, A. Shah, and Y. Bengio. Unitary evolution recurrent neural networks. In International conference on machine learning, pages 1 1120-112 1128. PMLR, 2016.
H. Bai, W. Zhang, L. Hou, L. Shang. J. Jin, X. Jiang, Q. Liu, M. Lyu, and I. King. BinaryBert: Pushing the limit of BERT quantization. In International Joint Conference on Natural Language Processing, pages 4334-4348, 2021.
Y. Bengio, N. Léonard, and A. Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint 0tt.::::30.33433 2013.
J. Bolte and E. Pauwels. Conservative set valued fields, automatic differentiation, stochastic gradient methods and deep learning. Mathematical Programming, 188:19-51, 2021.
A. Brock, J. Donahue, and K. Simonyan. Large scale gan training for high fidelity natural image synthesis. In International Conference on Learning Representations, 2018
W. Chan, N. Jaitly, Q. Le, and O. Vinyals. Listen, attend and spell: A neural network for large vocabulary conversational speech recognition. In IEEE international conference on acousties, speech and signal processing, pages 4960-4964. IEEE, 2016.
K. Cho, B. van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio. Learning phrase representations using RNN encoder-decodee for statistical machine translation. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, page 1724, 2014.
M. Cisse, P. Bojanowski, E. Grave, Y. Dauphin, and N. Usunier. Parseval networks: Improving robustness to adversarial examples. In International conference on machine learning, pages 854 863. PMLR, 2017.
M. Courbariaux, Y. Bengio, and J.-P. David, BinaryConnect: Training deep neural networks with binary weights during propagations. Advances in Neural Information Processing Systems, 28, 2015.
https:: wwwp:///wwww//..o//./////./..... dew..deel.... Jeel.ai/ /i/

---

Published conference paper at ICLR 2025
M. Courbariaux, Hubara, D. Soudry, R. El- El-Yaniv, and Y. Bengio. Binarized neural networks: Training deep neural networks with weights and activations constrained to +1 -1. arXiv preprint (0Xx::1022.02830, 2016.
W. De Launey and D. M. Gordon. A comment on the hadamard conjecture. Journal of Combinatorial Theory Series A, 95( 95(1):180-184, 2001.
J. Devlin. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint
2018.
J. Devlin, R. Zbib, Z. Huang, T. Lamar, R. Schwartz, and J. Makhoul. Fast and robust neural network joint models for statistical machine translation. In Proceedings of the 52nd annual meeting of the Association for Computational Linguistics, pages 1370-1380, 2014.
N. B. Erichson, O. Azencot, A. Queiruga, L. Hodgkinson, and M. W. Mahoney. Lipschitz recurrent neural networks. In International Conference on Learning Representations, 2021.
A. Foucault, F. Mamalet, and F. Malgouyres, Quantized approximately orthogonal recurrent neural networks. arXiv preprint arXiv:2402.0444 044022 2024.
E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh. OPTQ: Accurate quantization for generative
pre-trained transformers. International Conference on Learning Representations, 2023.
A. Gholami, S. Kim, D. Zhen, Z. Yao, M. Mahoney, and K. Keutzer. A survey of quantization methods for efficient neural network inference. In Low-Power Computer Vision, chapter 13, pages 291-326. Chapman and Hall/CRC, 2022.
X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. In International Conference on Artificial Intelligence and Statistics, pages 249-256. JMLR Work- shop and Conference Proceedings, 2010.
A. Gu, K. Goel, and C. Re. Efficiently modeling long sequences with structured state spaces. In International Conference Learning Representations, 2022.
Hadamard. Resolution d'une question relative aux determinants. Bull. des sciences math., 240-246. 1893.
Q. He, Wen, S. Zhou, Y. Wu, C. Yao, Zhou, and Zou. Effective quantization methods for recurrent neural networks. arXiv preprint arXiv: 10176 2016
A. Hedayat and W. D. Wallis. Hadamard matrices and their applications. The Annals of Statistics, (6):1 101l1884-2888 1978.
K. Helfrich, D. Willmott, and Q. Ye. Orthogonal recurrent neural networks with scaled Cayley transform. In International Conference on Machine Learning, pages 1969-1978, PMLR, 2018.
G. Hinton. Neural networks for machine learning. Coursera, video lectures, 2012. Lecture 15b.
Hochreiter and J. Schmidhuber. Long short-term memory. Neural computation, 98):1735--780,, 1997.
K. Horadam. Hadamard Matrices and Their Applications. Princeton University Press, 2007.
L. Hou, Q. Yao, and J. T. Y. Kwok. Loss-aware binarization of deep networks. In International Conference on Learning Representations, 2017.
I. Hubara, M. Courbariaux, D. Soudry, R. El-Yaniv, and Y. Bengio. Quantized neural networks: Training neural networks with low precision weights and activations. Journal of Machine Learning Research, 18(1 0:6869-68998 2017.
L. Jing, Y. Shen, T. Dubcek, J. Peurifoy, S. Skirlo, Y. LeCun, M. Tegmark, and M. Soljačić. Tun- able efficient unitary neural networks (EUNN) and their application to RNNs. In International Conference Machine Learning, 2017.
12

---

Published conference paper at ICLR 2025
C. Jose, M. Cissé, and F. Fleuret. Kronecker recurrent units. In International Conference on Machine Learning, 2018.
B. Kiani, R. Balestriero, LeCun, and S. Lloyd. projUNN: efficient method for training deep networks with unitary matrices. Advances in Neural Information Processing Systems, 35, 2022.
D. Kingma and J. Ba. Adam: method for stochastic optimization. In International Conference on Learning Representations, 2015.
D. Kingma and P. Dhariwal. Glow: Generative flow with invertible Ixl convolutions. Advances in neural information processing systems, 31, 2018.
A. Kusupati, M. Singh, K. Bhatia, A. Kumar, Jain, and M. Varma. FastGRNN: fast, accurate, stable and tiny kilobyte sized gated recurrent neural network. Advances in Neural Information Processing Systems, 31, 2018.
M. Przcano-Casadee D. Martinez-Rubio, and D. Martínez- Rubio. Cheap orthogonal constraints in neural networks: A simple parametrization of the orthogonal and unitary group. In International Conference Machine Learning, 2019.
Z. Lin, M. Courbariaux, R. Memisevic, and Y. Bengio. Neural networks with few multiplications. 2015.
arXiv preprint
X. Liu, D. Cao, and K. Yu. Binarized LSTM language model. In Conference the North American Chapter of the Association for Computational Linguistics, 2018.
Z. Liu, B. Oguz, A. Pappu, I.. Xiao, S. Yih, M. Li, R. Krishnamoorthi, and Y. Mehdad, BiT: Robustly binarized multi-distilled transformer. Advances in Neural Information Processing Systems, 2022.
Z. Liu, B. Oguz, C. Zhao, F. Chang, P. Stock, Y. Mehdad, Y. Shi, R. Krishnamoorthi, and V. Chandra. LLM-QAT: Data-free quantization aware training for large language models. arXiv preprint arXiv:2305. 178888 2023.
A. Maas, R. E. Daly, P. T. Pham, D. Huang. Ng, and C. Potts. Learning word vectors for senti- ment analysis. In Proceedings of the 49th annual meeting of the Association for Computational Linguistics: Human language technologies, 2011.
M. P. Marcus, B. Santorini, and M. A. Marcinkiewicz. Building large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2)3313-330 1993.
Z. Mhammedi, A. D. Hellicar, A. Rahman, and J. Bailey. Efficient orthogonal parametrisation of recurrent neural networks using Householder reflections. In International Conference on Machine Learning, 2017.
V. Nia, E. Sari, V. Courville, and M. Asgharian. Training integer-only deep recurrent neural networks. SN Computer Science, 4(5):501, 2023.
D. 2. Doković, O. Golubitsky, and S. Kotsireas. Some new orders of hadamard and skew-hadamard matrices. Journal combinatorial designs, 22(6):270- 277, 2014.
A. Orvieto, S. L. Smith, A. Gu, A. Fernando, C. Gulcehre, R. Pascanu, and S. De. Resurrecting recurrent neural networks for long sequences. In International Conference on Machine Learning, 2023.
J. Ott, Z. Lin, Y. Zhang, S.-C. Liu, and Y. Bengio. Recurrent neural networks with limited numerical precision. arXiv preprint arXiv: 100v::660.000 16902 2016.
R. Pascanu, T. Mikolov, and Y. Bengio. On the difficulty of training recurrent neural networks. In International Conference Machine Learning, 2013.
H. Qin, Y. Ding, M. Zhang, Q. YAN, A. Liu, Q. Dang, Z. Liu, and X. Liu. BiBERT: Accurate fully binarized BERT. In International Conference on Learning Representations, 2022.
13

---

Published conference paper at ICLR 2025
T. K. Rusch and S. Mishra. Unicornn: A recurrent model for learning very long time dependencies. In International Conference on Machine Learning. 2021.
Shen, Z. Dong, Ye, L.. Ma, Yao, Gholami, M. W. Mahoney, and K. Keutzer. Q-bert: Hessian based ultra-low precision quantization of bert. AAAI Conference on Artificial Intelligence, 2020.
Stock, A. Fan, B. Graham, E. Grave, R. Gribonval, H. Jegou, and A. Joulin. Training with quantization noise for extreme model compression. In International Conference on Learning Representations, 2021.
7. Sun, H. Yu, X. Song, R. Liu, Y. Yang, and D. Zhou. MobileBERT: a compact task-agnostic BERT for resource-limited devices. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020.
I. Sutskever, O. Vinyals, and Q Le. Sequence to sequence learning with neural networks. Advances in Neural Information Processing Systems. 2014.
J. Sylvester. LX. Thoughts on inverse orthogonal matrices, simultancous sign successions, and tessellated pavements in two more colors, with applications to newton's 's rule, ornamental tile- work, and the theory of numbers. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 34(232):461
1867.
Y. Tay, M. Dehghani, S. Abnar, Y. Shen, D. Bahri, P. Pham, J. Rao, L. Yang, S. Ruder, and D. Metzler. Long range arena: A benchmark for efficient transformers. In International Conference on Learning Representations, 2020.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. Advances in Neural Information Processing systems, 30, 2017.
E. Vorontsov, C. Trabelsi, S. Kadoury, and C. Pal. On orthogonality and learning recurrent networks with long term dependencies. In International Conference on Machine Learning, 2017.
A. Wang, A. Singh, J. Michael, F. Hill, O. Levy, and R. Bowman. GLUB: A multi-task benchmark and analysis platform for natural language understanding. In International Conference on Learning Representations, 2019.
P. Wang, X. Xie, L. Deng, G. Li, D. Wang, and Y. Xie. Hitnet: Hybrid ternary recurrent neural network. Advances in Neural Information Processing Systems, 2018.
S. Wisdom, T. Powers, J. Hershey, J. Le Roux, and L. Atlas. Full-capacity unitary recurrent neural networks, Advances in Neural Information Processing Systems, 2016.
H. Wu, J. Xu, J. Wang, and M. Long. Autoformer: Decomposition transformers with correlcornlltion for long-term series forecasting. In Advances neural information processing systems, 2021.
G. Xiao, J. Lin, M. Seznec, H. Wu, J. Demouth, and S. Han. Smoothquant: Accurate and efficient post-training quantization for large language models. International Conference on Machine Learning, 2023.
C. Xu, J. Yao, Z. Lin, W. Ou, Y. Cao, Z. Wang, and H. Zha. Alternating multi-bit quantization for recurrent neural networks. In International Conference on Learning Representations, 2018
Z. Yao, R. Yazdani Aminabadi, M. Zhang, X. Wu, C. Li, and Y. He. Zeroquant: Efficient and affordable post-training quantization for large-scale transformers. Advances in Neural Information Processing Systems, 2022.
A. H. Zadeh, I. Edo, O. M. Awad, and A. Moshovos. Gobo: Quantizing models for low latency and energy efficient inference. IEEE/ACM International Symposium Microarchitecture (MICRO), 2020.
nlp
O. Zafrir, G. Boudoukh, Izsak, and M. Wasserblat. Q8bert: Quantized 8bit bert. In Workshop on Energy Efficient Machine Learning and Cognitive Computing-Neuriee 2019.
14

---

Published conference paper at ICLR 2025
Zhang, Q. Lei, and Dhillon. Stabilizing gradients for deep neural networks via efficient svd parameterization. In International Conference Machine Learning, 2018.
W. Zhang, L. Hou, Yin, L. Shang, X. Chen, X. Jiang, and Q. Liu. Temarybert: Distillation-awer awaaee ultra-low bit bert. In Conference on Empirical Methods in Natural Language Processing, 2020.
H. Zhou, S. Zhang, Peng, S. Zhang, J. Li, H. Xiong, and W. Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting, AAAI conference on artificial intelligence. 2021.
S. Zhou, Y. Wu. Z. Ni, X. Zhou, H. Wen, and Y. Zou. DoReFa-net: Training low bitwidth convolu- tional neural networks with low bitwidth gradients. arXiv preprint 16X.::6606006666 2016.
S.-C. Zhou, Y.-Z. Wang, H. Wen, Q.-Y. He, and Y.-H. Zou. Balanced quantization: An effective and efficient approach quantized neural networks. Journal of Computer Science and Technology. 32:667-682, 2017.
Zhou, Z. Ma, Q. Wen, X. Wang, L. Sun, and R. Jin. Fedformer: Frequency enhanced decomposed transformer for long-term series forecasting. In International conference on machine learning. 2022.
15

---

Published conference paper at ICLR 2025
A BIBLIOGRAPHY ON ORNNS
This appendix provides a detailed bibliography on unitary and orthogonal recurrent neural networks.
Unitary Recurrent Neural Networks (URNNs) were introduced in Arjovsky et al. (2016) capture long-term dependencies more effectively than LSTMs. Several methods have been developed to parameterize recurrent weight matrices in URNNs and orthogonal RNNs. These include using the Cayley transform (Wisdom et al. 2016; Helfrich et al., 2018), Givens rotations (Jing et al. 2017), Householder reflections (Mhammedi et al. 2017), Kronecker matrices (Jose al., 2018 soft- orthogonality (Vorontsov et al., 2017). the Singular Value Decomposition (SVD) (Zhang et al. 2018 the exponential map (Lezcano- Casooo et al. 2019), and Riemannian optimization strategies (Kiani et al. 2022). Each method aims to improve model expressivity, efficiency reducing complexity.
The only known attempt to quantize ORNN weights is detailed Foucault et al, (2024). This method enables the learning of challenging tasks, such as the copy task for 1000 timesteps, using bits for the weights and 12 bits for the activations.
B PROOFS
We begin this section by reviewing the definition and proposition the Kronecker product. Then for completeness, in Appendix B.2 we provide the proof of Proposition 3.2 and, Appendix B33 provide the proof of Proposition 3.3
B. REMINDERS ON THE KRONECKER PRODUCT
Definition B.1. Let P. q. E N Let A = (aij),, E RR and B E Rrxs, The Kronecker product
of A by B, denoted A & B, is the matrix of size pr X given by
91 B
11g
B
& B =
Apt B
ap
B
The following proposition states well-known result concerning the Kronecker product.
Proposition B.2. Let p.q.r. s E N". Let p2 and E Ik If the lines of A are pairwise orthogonal and the lines of B are pairwise orthogonal, then the lines of A 8 B are pairwise orthogonal.
We provide the proof for completeness.
Proof. Let A R and B E Ress be two matrices. We denote A, R (resp B, R the ,h line of A (resp B). Assume that for all (i E []. satisfying # A,A) = O. Assume also that for all (m, n) E r satisfying m # n, B B', = 0. The hypotheses imply that there AA' = diag(a)
R2 and & E R' such that
and
BB (f)
Denoting
=
0 B
an B
Q B
a
B
pq B
For any (i.j) E [1. using block matrix multiplication, the block size r X r at position (t. of CC is
(a BXa, BY Σ a diag( diag(a);, diag( =
O
if
diag(
if
1=1
Therefore CC' = diag(a & B) and the lines of A 2 B are pairwise orthogonal
16

---

Published conference paper at ICLR 2025
B.2 PROOF PROPOSITION 3.2
We proceed by induction.
Initialization: Consider k 1. Using the definition of 22, we have
11) -1 =12
))
S2 2
Therefore the lines of S2 are pairwise orthogonal. Since S2 is square and its components in 1-1,+1). S2 is a Hadamard matrix.
Heredity: Consider k 2 1 and assume that Sze is Hadamard matrix. We want to prove
24
S2
that S2411
is Hadamard matrix.
24
Syt
Notice first that since Sze is Hadamard matrix, Syas is square and its components are in (-1,+1}. Using the definition of the Kronecker product, we also have
S2411
x Sy S2 S2*
-1
Since the lines of S2 are pairwise orthogonal and the lines of Syt are pairwise orthogonal, we can apply Proposition B.2 and conclude that the lines of S2401 are also pairwise orthogonal. We conclude that S a Hadamard matrix.
This concludes the proof by induction.
B.3 PROOF OF PROPOSITION 3.3
E and H E Hn We first show that ΦH is injective.
u, E [-1, 112h such that # u'. Let (l....., .n) be such that u, # u/, that is, since u; and u/ are both in (-1, 1), = -4, Denoting, for all matrix A, the i-th row of by A,, we obtain
(H(,;; u, H, n/ H, (
Since all the components of ( are in (-1, 1, 4 (4); # and finally (H("), # (H(4'), As conclusion, for any u,u' E 11 such that u # u', o (u) # (n(4') The mapping &u is injective.
We now show that (4) is Hadamard matrix. Notice first that (u) is square and that all its components are (-1,1). 1]. We still need to show that any two distinct rows of & Φ are orthogonal.
Let i.j [I. with i # Reminding that n (u); is i-th line of & z (u), have
&u ( u, H, H.= =0. 0.
Finally, (u) is Hadamard matrix.
This concludes the proof.
B.4 DETAILED PROOF OF THE ORTHOGONALITY OF THE BINARY AND SPARSE TERNARY WEIGHTS
The proof that the binary matrix defined by
W diag(u)S, Sy: e Rd,dd,
orthogonal when d, = is in Appendix sparse ternary matrix defined below is orthogonal. We only detail the latter proof.
The general proof is similar to the proof that the
17

---

Published conference paper at ICLR 2025
Let us prove that the sparse ternary weights defined by
(u))
diag(u) (1g @ Sze) E Rdoxd, 2
(5)
are orthogonal for all E (-1, 11d,, and d,; = q2".
To do so, consider E 1 We first remark that the lines of l are pairwise orthogonal. Because S2t is Hadamard matrix, the lines of S2t are also pairwise orthogonal. Applying Proposi- tion B.2 we conclude that the lines of 1g @ 22 are pairwise orthogonal. Therefore, the lines of W (u) are also pairwise orthogonal and the matrix (u) W (u) is diagonal. Let us consider E [[1 d we write (m 1)2* n, where [1. and [1,2*]] Reminding that W W(u), is the i-th line of W (4), and (S24), , is the n-th line of Sze, we have
(
( (((())))
(w())(())). = (w)) =
122
2
Sttt
Po.
=
2
j=l
because u, E (-1,1) and all the components Sze are in (-1,1). Finally, we conclude that W W())W())
(u) = 'd Because the matrix W (u) is square, we also have (u)) W/ (u) l and the matrix W (u) is orthogonal.
This concludes the proof the sparse ternary matrix defined by (5) is orthogonal.
C THE STRAIGHT-THROUGH ESTIMATOR AND AN EXAMPLE
We present the Straight-through Estimator (STE) in Appendix C.I and provide in Appendix C.2 detailed example of a recurrent weight matrix for the HadamRNN defined in Section 3.3 specifical when d,
C.I THE STRAIGHT-THROUGH ESTIMATOR
In this section, we discuss the Straight throggh Estimator, introduced in Hinton et al. (2013); Courbariax et al. (2015), a standard method for optimizing quantized neural network weights, in the context of HadamRNN and Hadcm.H.
(2012): Bengio
For simplicity, we omit the optimization of U, V, b, and b, in the following description, focusing on the recurrent matrix.
We consider matrix W E Rdxxd, For the HadamRNNs defined in Section 3.3 we use the constant orthogonal matrix W Sze, while for the Block- HadamRaa defined in Section 3.4 we take
vd
W (I, Sy).. As described in these sections, the only trainable parameter for the recurrent matrix the binary vector which defines the recurrent weight matrix diag(u)W.
V22
We will describe the STE method for optimizing E {-1, 114h, Therefore, we only consider learning objective L Rd R and the optimization problem
argmin L(u).
(6)
To optimize define the quantization operator H Rd - 1-1, 1)1, where, for all ā E Rdh
the vector (ū) E (-1,1)44 is given by
H(),, = {
+1 if ú, 2 0
for all i E E (1.....44 d,
-1 otherwise
18

---

the recurrent weight matrices are Published conference paper at ICLR 2025
The operator H surjective, since for all [-1,1]d, (u)) Therefore, 6 is equivalent to minimizing LoH over Rd,, To minimize L.H the STE applies modified gradient descent algorithm. The modification is described below.
The operator H is piecewise constant and its gradient at i, denoted
dh is either undefined or 0.
ab li
This issue is standard in quantization-ave aware training, which aims minimize the objective L(H (ū)
with respect to a. Backpropagating the gradient using the chain rule
dLoH du
aL
He
du
H())
du
either possible or results in null gradient in this context.
To address this issue, backpropagation through the quantization operator is performed using STE
Hinton (2012): Bengio al. (2013); Courbariaux al. (2015). The latter approximates the gradient using
HLoH
dL
2
du
du (())
as if d1l
C.2 EXAMPLE OF A RECURRENT WEIGHT MATRICE
For HadamRNN, with d, = 4, using 3 defined for u E [-1,+1}* by
and Proposition
3.2
U1
0
0
0
(
0
42
0
-1
-1
2
0
0
11
0
1
-1
0
44
The components of optimized using the STE, as described in Appendix
As mentioned in Section 3.3 and demonstrated in Appendix for the general case, can be verified
that, for all E [-1. JS, W()) is orthogonal, i.c. W (u))(nn) Id, Indeed, W W() (w) equals
42
0
15
0
0
00
4
11
44
-1
0
0
244
0
0
0
U2
0
0
0
11
0
4
0
0
0
44
4
44
0
0
dx
D EXPERIMENTS DETAILS
D.I COPY TASK
We generated 512K samples for the training set, and 2K samples for both validation and test. were trained using the Adam optimizer OptimizerKKingmaa Kingma and Ba (2015). We used batch size of 128 samples. The learning rate is initialized to le 4 decayed exponentially by applying factor 0.98 after each epoch. 10 epochs were used for training.
HadamRNN and Block-HadamRNN
19

---

Published conference paper at ICLR 2025
D.2 PERMUTED SEQUENTIAL MNIST
We used 50K samples for training. 10K samples for validation and 10K samples for testing. Hadam- RNN and Hoock-HadmRRNN were trained using the Adam optimizerKKingma and Ba (2015). We used batch size of 64 samples. The learning rate is initialized to le 3 is decayed exponentially by applying a factor 0.98 after each epoch. 200 epochs were used for training.
D.3 IMDB DATASET
The IMDB dataset contains 50, 000 samples. Among these, 25, 000 samples used for training, and the remaining 25, 000 are equally divided between validation and testing.
We used batch size of 100 samples. The learning rate is initialized Se- 4 decayed exponentially by applying a factor 0.99 after each epoch. 30 epochs were used for training.
E COMPLEMENTS ON THE EXPERIMENTS
E.1 TRAINING TIME
For each benchmark of Section and Appendix F.1 we provide the training time for the HadamRNN in T As the training times for the Block- HacckHHadmRNNN are comparable, they are not explicitly reported here. Experiments where done on NVIDIA GeForce RTX 3080 GPU. For comparison, BessGRNNNKKsuppee et al. (2018) requires 16.97 hours of training time on the MNIST dataset. The training times for the HAR-2 and DSA-19 datasets, along with a comparison to those of FastGRNN, are presented in Table 7
Table 4: Training times, in hours
dataset
Copy task
PMNIST / SMNIST
IMDB
SST-2
QQP
# epochs
10
200
30
60
50
training time (hr)
13
13
0.5
0.36
7.5
E.2 TRAINING STABILITY
In this section, examine the variability of the trained HadamRNN model based on different random initializations and randomness in the stochastic algorithm (Adam). The experiments were conducted using the IMDB dataset, with similar trends observed across the other benchmarks, supporting the consistency of these conclusions.
Each trainable matrix vector initialized using the Glorot initialization method Glorot and Bengio (2010), which relies on a random seed. For a fixed combination of bitwidth p (applied to the matrices 0 and V) and initial learning rate, train 5 different models using 5 different random seeds. The average performance and standard deviation of the models are reported in Table
As expected, the initial learning rate significantly influences the performance of the trained model. It appears that performance improves as the initial learning rate increases when decreases. In all cases, the optimal learning rate spans approximately one order of magnitude, suggesting that the search for the optimal initial learning rate can be conducted on exponential scale.
bitwidth of p = 2 results relatively high variability in the performance of the trained model, whereas bitwidths of p 4 and 6 exhibit negligible variance. As anticipated, smaller bitwidths on U and V matrices make the training process more sensitive to the random initialization of the parameters.
E.3 VISUALIZATION OF MODEL COMPARISONS
We provide two visual comparisons of HadamRNN, HadkmRa,,,,NN, QORNN, LSTM and ORNN based different criteria, using data from Table 2 and Table
20

---

Published conference paper at ICLR 2025
Table 5: HadamRNN's training variability over 5 experiments on the IMDB dataset, for each combination of bitwidth for the matrices U and V, and initial learning rate.
U & V bitwidth
Initial learning rate
Average performance
Standard deviation
1.c-2
83.28
1.00
5.c-3
83.83
1.36
1.e-3
80.84
5.09
5.e-4
80.75
8.05
1.c-4
74.61
2.69
l.e-2
83.76
0.70
5.e-3
83.73
0.40
1.e-3
85.83
0.40
5.e-4
85.85
0.39
1.e-4
83.05
0.49
I.c-2
83.18
1.88
5.c-3
83,61
0.53
1.e-3
85.73
0.63
5.e-4
86.09
0.35
1.e-4
83.47
0.50
97-
26.
HRNM
Accuracy
85
HBNN.
04-
ODAN
HRNN
10'
10a
12F
Model size (kBytes) log scale
Position of each model in the (size, performance) plane, on PMNIST. The most effective models located in the upper-left corner of Figure] [ The parameter p corresponds to the bitwidth of the quantized matrices U and V, as introduced in Section 3.5 FP stands for full-precision.
Figure 1:
In Figure 1 plot each model in the (size, performance) plane, where size is measured in kilobytes (kB) and performance corresponds to the accuracy of the trained model on PMNIST. The most effective models are located in the upper-left corner of Figure The plot highlights the efficiency of HadamRNN.
In Figure we plot the HadamRNN and Hackk-Ha models for different values of q the (complexity, performance) plane. Complexity measured by the number of fixed- point precision additions (see Table I), while performance corresponds the cross-entropy the trained model on the Copy task. The most effective models appear in the lower-left corner of Figure 2
This visualization highlights that, for the Copy task, g can tuned to balance the trade-off between complexity and performance.
21

---

Published conference paper at ICLR 2025
10
DHIRM
10a*
10a
Complexity (number of fixed point precision additions) log scale
Figure 2: Position of HadamRNN and Block-HadamRNN models for different values of q in the (complexity, performance) plane. The most effective models appear the lower-left corner of Figure The bitwidth of the quantized matrices U and V is set 4.
F MORE BENCHMARKS
In Appendix F. we provide comparison of HadamRNN and quantized versions of BERT on the SST-2 and QQP benchmarks from GLUE (Wang et al. (2019). In Appendix F.2 provide results on IoT task benchmarks: HAR-2 and DSA-19 as described Kusupati et al. (2018).
F.1 GLUE BENCHMARK AND COMPARISON WITH TRANSFOR
GLUE is a well-established benchmark for NLP systems, comprising various sentence-level language understanding tasks. The most effective solutions for these tasks are large models trained extensive datasets, typically large pretrained language models (LLMs) followed by fine-tuning with a task- specific head.
Although HadamRNN and Block- Boock-HadaRRNN are not designed to operate within a large language model (LLM) framework, and ORNN results reported on the benchmark leaderboard, evaluate the performance of HadamRNN and Block-HadamRNN trained directly on the training data of single task. This allows position these networks relative to transformer-based models.
We selected two tasks: SST-2, sentiment analysis task closely related to the objective of the IMDB dataset, and QQP (Quora Question Pairs), which evaluates whether two questions semantically equivalent. For both tasks, as is standard practice, we used tokenizer to map sentences into sequences of indices, padded fixed length of 128 timesteps. For sentence pairs, as recommended (and done in the reference code), we concatenated both sentences with two separator tokens in between.
Each task was trained using the respective training dataset without data augmentation. The network achieving the best score on the validation dataset was retained, and its predictions were submitted to GLUE Benchmark website. The performance metries provided by the website are reported in Table 6
Since HadamRNN and Block-HHddmmee are trained exclusively on the training data for a single task, larger networks tend to overfit. Notably, were unable train and generalize effectively validation data using pre-trained embeddings, such as the first layer of BERT (with a size of 768). Instead, used trainable embedding layer of size 256.
For the SST-2 task, the best results were achieved with an HadamRNN network having a hidden size of 128. resulting in total model size of approximately kB and accuracy of 81.9%. In comparison, the smallest BiBERT model, distilled from a BERT pre-trained on a large dataset and with network size 550 times larger, achieves 85.4%.
22

---

Published conference paper at ICLR 2025
Table 6: Performance comparison of HadamRNN, Mlock-HadamRNN, and state-of-the-rt models on two GLUE benchmark tasks: SST-2 and QQP. The last column indicates the model size in kilobytes (kB).
Model
Performance
Size
kBytes
SST-2 task
128, d.w accuracy)
Q8BERT
Zafrir et al. 2019
92.24
110 0D0
Q-BERT
Shen
2020
92.08
48 100
TemaryBERT
(Zhang ct al.
2020
92.8
000
MobileBERT
(un ct al.
2020
91.6
15 100
BinaryBERT BBr el
2021
92.3
13 400
BiT (Liu et al. 20222
89.9
13 400
BiBERT (Qnn et al.
(2022
88.7
43.400
BiBERT (Qin ct al
2022
87.9
800
BiBERT [Qin et al
2022
85,4
4.00
HadamRNN (ours, d,
256, d₂ 128)
81.9
8
QQP task (T 128, d 1. accuracy)
QSBERT Zafrir et al. 2019
87.96
110 000
Temary BinaryBEEse BKT Zhang et al 2020
88.8
18 000
BinaryBERT (Bar
88.9
13:400
BIT (Liu et al. (022)
85.4
13:400
BiBEKT (Qin ét
2022
84.8
13:400
BiBERT (Qin ct al.
2022
83.3
800
BiBERT (Qin et
2022
78.2
400
BNNck-N (ours,
256. d, 512, == 128)
82.1
33
For the QQP task, using Block-HadamRNNN network with hidden size of 512 and block size of 128, we obtained an accuracy of 82.1%. This result surpasses the smallest BiBERT, despite our model being more than 130 times smaller.
F.2 INTERNET THINGS (IOT) BENCHMARKS
HadamRNN and Hadckma are particularly well-suited for modeling long-term dependencies such as the Copy task, thanks to their orthogonal recurrent weight matrix. To provide a comprehensive evaluation, we also tested these models on two short-term memory 1oT benchmarks (< 150 timesteps), previously addressed by FastGRNN Kusupati et al. (2018). The results of these experiments are summarized in Table 7 For both benchmarks, the hyperparameter in Block- Block-HadamRNe (detailed in Section 3.4
optimized using grid search.
Human Activity Recognition (HAR-2) The Human Activity Recognition (HAR) dataset consists of human motion data captured using an accelerometer and gyroscope embedded Samsung Galaxy S II smartphone. Data is recorded at fixed frequency of 50 Hz, with each sequence spanning 128 timesteps. Each sequence is labeled with one of the following six activity classes: Sitting, Laying, Walking Upstairs, Standing, Walking, and Walking Downstairs. Following the approach in Kusupati ct al. 2018), these six classes are grouped into two categories: (Sitting, Laying, Walking Upstairs) and Standing, Walking, Walking Downstarrs). The objective is classify each sequence into the correct category. Both the training and test sets have been preprocessed to ensure zero mean and unit variance, ensuring consistency across the data.
Daily and Sports Activity (DSA-19) This dataset comprises motion sensor data collected from accelerometers, gyroscopes, and magnetometers, capturing a range of daily and sports- human activities. Mcasurements 125 timesteps. A total 19 distinct activities were performed by the participants, with each sequence labeled according to its corresponding activity type. The objective is to accurately predict the activity
sampled at fixed frequency of 25 Hz and segmented into sequences of
23

---

Published conference paper at ICLR 2025
Table Comparison of performances of the HadamRNN, the Block-HadamRNN and FastGRNN Kusupati et al. 2018)) on two IoT benchmarks (HAR-2 and DSA-19). Last column reports the model size kBytes.
Model
d
train time (min)
W bitwidth
& V bitwidth
performance
size
kBytes
HAR-2
128, d,- dme accuracy)
FastGRNN (Kusupati al. 2018
80
4.8
8
95.59
3.00
12.1
4
94.81
9.13
1024
12.5
95.76
11.63
10.2
95.36
14.13
Block- Hacc-HHdmmRNN
12.0
4
94.87
4.37
512
12.1
1
6
94.56
5.82
12.2
95.64
7.07
4.4
4
83.40
4.57
HadamRNN
512
5.2
84.45
5.82
4.2
8
84.11
7.07
DSA-19
125, d 45, d
19, accuracy)
FastGRNN (Kusupati al.
2018
80
2.2
8
85.67
22.00
5.1
4
76.51
9.11
256
78.30
13.11
3.0
8
75.5
17.11
Block- NookkHHddmRNNN
5.2
4
81.32
18.14
512
6.2
1
85.26
26.14
3.2
81.86
34.14
5.2
4
77.93
18. 14
HadamRNN
512
3.4
76.01
26.
3.3
8
79.12
34.14
associated with each sequence. Both the training and test sets have been preprocessed to achieve zero mean and unit variance, ensuring consistency across the data.
Our results show that an optimized Block-HadamRNN delivers performance comparable to Fast- GRNN while maintaining a similarly compact model size. For instance, on DSA-19 benchmark, the best Block- Block-HadamRN1 model achieves performance within approximately 0.4% of FastGRNN, with a comparable size. Notably, on the HAR-2 benchmark, the Block-Had outperforms FastGRNN in performance with only marginal size increase of few kilobytes. These findings suggest that HadamRNN and Block-HadamKNN are also well-suited for tasks where long-term memory capabilities not critical requirement.
G LINEAR VERSUS RELU RECURRENT UNITS
In this appendix, argue that 'INNaa'-ONNs' considered in Section 3.1 are better suited than 'ReLU-ORNNS' for tasks that require strong memorization. An ablation study supporting this fact is in Appendix G. The theoretical arguments given in Appendix G.2.1 and the experimental arguments are in Appendix G.2.2
Throughout the appendix, consider h, 0, matrix U E Rdaxdin and matrix V Ra E dh bo Rur, an orthogonal recurrent weight matrix W E Rdyxda and the ReLU activation function ø. We also consider inputs XI. E Rd
We call limear-ORNNs, those computing the sequence of hidden states h! hlln E Rd according to
hiinn W With + Ux, + b,-
24

---

Published conference paper at ICLR 2025
The output is the vector Vo(h + b, E Rda..
We call ReLU-ORNNs, those computing sequence of hidden states R Rd according to
n ReLLU
h Re h Ux, + b,).
(8)
The output is the vector Vh V
ReLU + b, E Rdm.
Notice that, for simplicity, we only consider many-to-one RNNs.
G.1 ABLATION STUDY
We compare the performance of HadamRNN with linear recurrent units, as described in the article, ①1) and (7), with those of HadamRNN with ReLU recurrent units, in (8), which we refer as HadamRNN-Rel. The results are summarized in Table g It can be observed that the HadamRNN- ReL.U fails to learn the copy task, and obtains poor results the other benchmarks, compared to the HadamRNN. This is because HadamRNN better memorize than HadamRNN-ReLU, This phenomenon is analyzed in Appendix G.2
Table Ablation study: performance comparison between HadamRNNs with linear recurrent units and with classical ReLU activation function recurrent unit. All results are presented with the size d, reported in Table and 4-bit quantization for and matrices. BL (baseline) means that the model failed to learn.
Model
Copy-task
PMNIST
SMNIST
IMDB
HadamRNN
1.6e-7
94.88
96.63
87.43
HadamRNN-ReLLU
BL
86.82
65.06
72.68
G.2 BETTER MEMORIZATION OF LINEAR RECURRENT UNITS
G.2.1 THEORETICAL ARGUMENTS
In this section, we analyze first for linear-ORNNs, then for ReL.U-ORNNs, the impact on the result
dadie and then compute of modification of the input x,. for [1,7]. To do so, first compute ax, oh and compare the behavior of the two quantities.
dx,
The linear-ORNN case
We consider an input sequence (x (x....., xy) E RR ,1 E [1,7] and
z = (0. (..... 2, 0. ......)) 0) RdaxT We denote hlj" the last hidden state computed at x and 8 the one computed + z. We show by induction that
g = h1"" + WT-
(9)
The impact of the perturbation is independent of x. The timestep influences WT- but has no impact on the norm of the variation since, as W is orthogonal,
|| I T-U,,, = ||U,,11
In conclusion, linear-ORNN retains information regardless of when the information occurs in the input sequence.
The ReLU-ORNN case Again, we consider an input sequence x (x.....,
I E [1, and z = (o.....o. z, ..... 0) E R We denote n Re the last hidden state computed and o ReLU the computed + Due the non-linear activation function, it is possible to derive a straightforward formula analogous to (9). To analyze the behavior of 87 first-order Taylor expansion and analyze its Jacobian.
Ret.U we use its
25

---

Published conference paper at ICLR 2025
For E [I,.... T), the Jacobian of h Rel. with respect x, writes
oh ReLL
dh oh
Re
R
dh ReLU
++2
:+1
dx,
dh ahRett
dh ah 1+1
dx,
W ... D1+1 W D,U E R
where, for all s, D, = diag (o' [Wh,--+ +Ux, + b,)) E {0, 1dddd is diagonal.
The Euclidean norm of vector is preserved when multiplied by W but most often decreases when multiplied by a matrix D,, since the latter often contains zeros on its diagonal. As a result, we expect the influence of variations of x,, for small, diminish or become negligible. Considering x, variation of O, we see that the first inputs may have less influence on the result than the later ones.
G.2.2 EXPERIMENTAL RESULTS
We conducted experiment to empirically demonstrate that linear-ORNNs have better memory retention than ReLU-ORNNs.
Setup We construct a HadamRNN, a lincar-ORNN, and consider the ReLU-ORNN obtained using the same weight matrices. They differ solely in the position of activation function (see 7 and (8). For given inputs Xy E (Rd,,, we denote the hidden state at time t as hlin and ReLU for 1= I...... T.
Our aim is to empirically observe that, regardless of f, a perturbation in the 1-th input has a consistent impact on the final hidden state hnfi.. In contrast, the impact of the same perturbation on the final hidden state h h.ReLU of the ReLU-ORNN diminishes as decreases. As the time difference increases, the model gradually loses information.
To this end, we generate 2-dimensional time series (xp...., ) E 2xT with T = 200 timesteps. We set xg (0, 0) and for I,..., T, sample x, according the Gaussian distribution N (x,-1- 12)
We set d, 128- = 2", and we let the Hadamard recurrent weight matrix be W Sy, as in Vdg
3). The components of the input matrix E R 128x2 are independently sampled from the normal distribution (0, 1). Since primary focus is on how input variations affect the hidden state, omit the output layer in our model.
The experiment To compute elin and eReLU E ERT, we apply a perturbation to x, along the first axis, for all I....,, T, and compute
eiin =x xp...., x7) 1 x, + (1,0),...,xTlll eReLU |lAReLU
(10)
x7) hReLU .x,,...,,, (1,0). x7)11
To compute plin and PROLU RT, we apply the same perturbation along the second axis, and compute
flin [x,, X, .......y. ... h!"" (x,..... x, + (0, 20 ,x,,,,,,
(11)
p. PROLU [IhRelit (x....... N,,
x,) .x.................. .......p'' ReLU (x,,...,X, , + (0, 1), ..... ...... Xy lll-
We plot the corresponding curves in Figure As predicted by the analysis of Appendix G.2. for the linear-ORNN, the magnitude of the difference hidden states remains constant, whether the perturbation is applied along the first or second axis. Conversely, in the ReI.U-ORNN case, the norm increases, possibly approaching O. This illustrates the fact that variations in x, have a diminishing impact the hidden state hy as T increases.
'For clarity, we use partial derivative notation for Jacobian matrices when applying the chain rule. It is important to note that while ReL.U is not differentiable at 0 in the traditional sense, the calculations remain rigorous (Bolte and Pauwels 202T
26

---

Published conference paper at ICLR 2025
1st direction
2nd direction
2.0
2.0
1.5
1.0
0.5
0.5
25
50
75
100
125
150
175
200
0
25
50
75
100
125
150
175
200
1.0
0.5
0.0
0.0
0
25
50
75
100
125
150
175
200
0
25
50
75
100
125
150
175
200
Figure 3: Top: elia and plin, bottom: ReLU and f RRLU see
TO and (11)
Conclusion Linear-ORNNs have better memorization property than ReLU-ORNNs, and are able to retain information over arbitrarily long delays. This information may be lost after certain delay with ReLU-ORNN.
H SWITCHING COLUMNS SIGNS NOT USEFUL
H.1 SWITCHING COLUMNS SIGNS DOES NOT PROVIDE MORE EXPRESSIVENESS
In this section, we first provide first result stating that modifying the signs of the lines of a Hadamard matrix (as is done by the multiplication by diag(u). in Proposition 3.3 and the definition of the W(u)s in (3) and (4)) defines the same hidden states as switching the signs of the columns. We then state that changing the signs of both rows and columns still defines the same hidden states and is therefore unnecessary.
To do so, we define, for and d No and given matrix E Rd the operator &H by:
Φu 111,1)dm
R a - diag(u) 11
and, for H E Rxddh, the operator HH by
HH : 1-1, nxd
II diag(u).
Proposition H.1. Let H Rdidd, E Rddxdin E Rouuddn and b, E Rdd.
For all u 1,,,, the RNNs states h, and W1 defined for all x Xx Rd by
h = Φn Ux, + b,
for all all E [1,T] nn) (u)x, + &r (4) for all E [1,T]
with ho = -16-- O, differ only by their sign:
h = diag(u)h, for all E [1,7]]
Proof. Consider H E Rdxxds U Kd V E Rd xda and b, E Rdh, Let X Xp..., Xy E Rdv,
Let us first prove that for all u E (-1, 1)dh and all E [[. h = diag(u)h, Let us consider u and prove that the result holds by induction.
27

---

Published conference paper at ICLR 2025
Table Comparison the performances of the linear HadamRNN in which only the rows switches are learned, and the linear HadamRNN in which both rows and columns switches are leamned. W is binary, and U and are quantized over 4 bits.
Model
switches and column switches
copy task
1.6c-7
1.3c-8
Permuted MNIST
94.88
28.99
Scquential MNIST
96.63
96.31
IMDB
87.43
85.24
Initialization: We have H/ diag(u)0 diag(u)ho-
Heredity: Assume 2 1 is such that nー diag(u)
Using the definition of h,, the fact that diag(u) la, and the definition of h, have
ny [H(w)/ +, (u)
H diag(u) diag(u) + diag(u)U diag(u),,
diag(u) (diag(u) + Ux, + b,)
= hiag(u)h,
This concludes the proof of the proposition.
This proposition ensures that, when optimizing and b, over a set that invariant under multiplication by diag(u) (whether the left or right), choosing left right yields equivalent hidden states.
Applying Proposition H.l to H' diag(w') H, for a fixed u' E {-1, 11d,, shows that changing the signs of both rows and columns results in the same hidden state as changing the signs of the rows only.
H.2 SWITCHING COLUMNS SIGNS ARMS RESULTS
We compared version of our linear HadamRNN where both row and column switches are learned during training, to the standard linear HadamRNN which only row switches are learned, as outlined in this paper.
The two versions of the models and the datasets use the same configurations as detailed in Section and Appendix D We used binary orthogonal recurrent weight matrix for W (see Section 3.3) and quantized U and V over 4 bits. Activations were not quantized.
Results are reported in Table 9 The standard version consistently outperforms the variant, except in the copy task. This finding, along with Appendix H.I supports our choice to learn row switches only.
I POST TRAINING QUANTIZATION OF ACTIVATIONS
I. REMINDERS ON FIXED-POINT ARITHMETIC
We follow conventional notations for fixed-point arithmetic: For integers q 2 0 and p the set of p-bit fixed-point numbers with bits allocated for the fractional part is represented as:
Qp.
1 1-2-1 1.-1
1] --22----,2---91 c R.
24
In the specific case where
= 1, we use the simplified notation:
2 = = =
1-2. 1
1
c l-1,1)
24
28

---

Published conference paper at ICLR 2025
The addition of two fixed-point numbers is only possible when they have identical fractional sizes. For example, if x and x' E q. then + x' E Qq+2.a
ng and x' E Qp.. results in value within x x' E Op Optp'-1atg" Thus, the product of x E 2g and x' edd satisfies x x' E a 2ate"
Multiplying two fxed-point numbers E Q
I.2 WEIGHT QUANTIZATION:
In the description of HadamRNN and Block-HadamRNN, matrices U E Rdixdi and V E P. [ddw Xdp
are quantized on p bits as described in Section 3.5 We will note q,(U)= au U (resp. 9p(V) (V) = ay V)
where the quantized matrix E p-1 Aaxdi Q
2n (resp. V E Qmm and dy = || max 0 p
(resp. ay || 0), where || max sup.y 1U,ي|-
Given the definition of W in and 4 note the recuirent matrix W dw W. with W E Q
and dw for Ha (or aw V2
2 for Block-HadamRNN)) Notice indeed that, since
vdn
2 1-1, 2' 2
1 0. ). all the matrices W in (-1, +1] dd (resp. V2 (-1,0, 0, +1 (dx)))) also in Vda
0 dxdda (resp.
(a Taking Qo = (-,, instead 2 does not permit the components
vdh
2
of yd
W (resp
to reach + (resp + 2x
2/2
vda
1.3 INPUT AND HIDDEN STATE ENCODING:
For each time step [[, the quantized hidden state h, is encoded using Pa bits, where Pa 1. fixed scaling factor a > is applied such that h = h, with h, E 0 ---1 We use the notation dn (x) to denote the closest element of x E R in Pp. This notation extends to vectors. qp,
In practice d, must be sufficiently large to cover the range of values for the full-precision hidden states. However, increasing a slightly may not significantly impact performance, allowing some flexibility in its selection.
Similarly, each input x,, for E [1,7]. is quantized using P bits, with Pt 1. For simplicity, continue to denote the quantized inputs as x,. Using fixed scaling factor a; > 0, we represent x, x where X, dmn
Input Quantization Examples:
For the copy-task where input entries are either 0 or 1, we use a; =2. As long as P; 2 2, quantization does not alter the inputs.
For the pixel-by-pixx MNIST tasks, with normalized 8-bit unsigned integer values in [0. 1]. we set a; 1. Quantization has no effect as long as p; 2
For the IMDB dataset, the 512 inputs are given by floating point word embedding prepro- cessing. We quantize these preprocessing outputs using p; Pa bits (i.e. within 2 and set a, to the maximum value of the embeddings.
1.4 INDEPENDENCE TO SCALING FACTORS
can be shown by induction that a vanilla (Linear or ReLU) RNN with parameters (W, ,b, U.V V. bb)) produces the same outputs as an RNN with parameters (W,2b, 2U, 2U, VV,,b)) b.)) for all 2 > O.
2b,
In the following sections, we use this idea and, instead of applying the network with quantized weights (W/,,, b 9, (U)) b,) (aw W. b, ay U. V. we rescale with 2 4.49 and apply the network with the parameters (aw W. b -ū uy b)). agay a
29

---

Published conference paper at ICLR 2025
Table 10: Value of aw and dn for activation quantification across the datasets and bitwidth.
U.V bitwidth
Copy-task
SMNIST
PMNIST
IMDB
Model
aw
aw
aw
aw 4
aw
awah
aw
aw
HadamRNN
4
0.088
2.0
0.044
4.0
0.044
1.0
0.044
8.0
1.5 RECURRENCE WITH FIXED-POINT ARITHMETIC:
Given, the quantized hidden state h, = = E a, Po-1" with a fixed value of dn chosen later, and the quantized input x, a, E a a p111"
The recurrence relation defined in I for the parameters (aw W, ___
a,ay ay V. b.) becomes:
aay
an h h, App aw WhWhh
1
Úx,
b
8;
a,ay
bj
= apa an aw W + Ux, + a,a+y
In this equation, the matrix-vector multiplications W h and Üx, are computed using fixed-point arithmetic.
We take advantage of the flexibility in choosing a, to ensure that multiplying by aw can be performed with simple bit shift. We first compute max, max |1 based on the full- precision hidden states from the training and validation datasets. We choose nn argmin (2" max; @w ), and set an = 2"h /aww
The values used in the experiments presented in Table TO
We also quantize the scaled bias using Pa bits.
Finally, the entry of the quantization dp, of which depends on dn and Pp+ Thus, h, can be computed using simple look-up table, eliminating the need for floating-pou -oint operations (division by an in 40.").
an a fixed-point value and thus belong to a finite set, the size
The quantization of the output layer follows the classical PTQ methodology, using a quantized value of the bias b, and the multiplicative factor a,0, ay.
This leads to a fully quantized RNN, The Table 2 shows that such fully quantized RNNs with = 12 bits achieve equivalent results than the RNNs with quantized weights only.
30


Reviews:
[{"review_id": "H8QJLPysJM", "reviewer": "Reviewer_fwft", "summary": "This paper proposes a method to parameterize the recurrent weights of Orthogonal Recurrent Neural Networks (ORNN), a special case of Vanilla RNN to binary or sparse ternary matrices. The binarization and sparse ternarization algorithms that the paper proposed are based on Hadamard Matrix Theory. The paper tests the algorithms on two types of binarized and sparse ternarized Orthogonal Vanilla Recurrent Networks and compares their performance to LSTMs and GRUs recurrent models for four standard benchmark datasets.", "questions": "- Could you evaluate the performance of Block-HadamRNN and HadamRNN on edge devices? In particular, would you be able to provide the speedup and computational overhead that while using your techniques on these devices?\n\n- Could you maybe think about making Tables 2 and 3 simpler to improve the readability of your results? Better visual perception may also result from the inclusion of a plot that contrasts the accuracy of all the suggested and benchmark approaches.\n\n- Could you maybe include a thorough example in the text that shows how a trained ORNN is subjected to the binarization or sparse ternarization algorithms? Could you also explain the Straight-Through Estimator's (STE) function in the parameterization process?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper proposes a novel approach to parameterize weights of Orthogonal RNN models using Hadamard Matrix Theory. As mentioned in the paper the binary and sparse ternary parameterization are investigated and analyzed on lightweight neural networks for time series, the results reported in Table 2 highlight the potential of the proposed approach by comparing to ORNN, LSTM and FastGRNN recurrent models.", "weaknesses": "The binarization and ternarization algorithms of Orthogonal Vanilla RNN are explained in sections 3.3 and 3.4 in a high-level way. Maybe providing a base example by giving the dimensions of the matrices to be binarized or ternarized would make the algorithms more transparent and easy to understand. \n\nThe results reported in Table 2 and Table 3 are tough to read. Maybe converting some of the results into plots would make it more straightforward for the reader to assess the paper's contributions. It is unclear where the advantage of using Hadamard Matrix Theory to parameterize the binary orthogonal recurrent weights lies .\nThe paper does not analyze the method proposed on any edge device. Reporting the overhead and the speedup obtained on HadamardRNN and Block-HadamardRNN would help assess the paper's contribution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EwhI98Kc4O", "reviewer": "Reviewer_gcYV", "summary": "Binary and sparse ternary weights in neural networks enable faster computations and lighter representations, facilitating their use on edge devices with limited computational power. However, to date, no method has successfully achieved binarization or ternarization of vanilla Recurrent Neural Network (RNN) weights. As a result, in this paper, the authors present a new approach leveraging the properties of Hadamard matrices to parameterize a subset of binary and sparse ternary orthogonal matrices. The method enables the training of Orthogonal RNNs (ORNNs) with binary and sparse ternary recurrent weights, effectively creating a specific class of binary and sparse ternary vanilla RNNs. Despite binarization or sparse ternarization, the proposed RNNs maintain performance levels comparable to state-of-the-art full-precision models, highlighting the approach's effectiveness.", "questions": "Summarizing: The proposal is interesting. However, the weaknesses presented in terms of state-of-the-art and comparison are not so minor. Therefore, this work needs more effort to be improved, and it is not ready for publication in this state.\n\nBased on the above, expanding the experiments and the related work to include additional competitors from Transformer-based models would significantly strengthen the paper's relevance and situate it better within the current research landscape.\n\nOther minor considerations: I recommend that the authors carefully re-read the work; there are several typos and English errors. Furthermore, the plots in the Appendix do not specify what the X-axis and Y-axis represent.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper is well-organized and has a high level of clarity in its writing and the presentation of its proposal.\n\nEach section flows logically, enhancing the reader's comprehension of the paper's purpose and methodology. Notably, sections 3 (+ the Appendix) stand out for its depth and precision, guiding the reader through the formality of the proposed approach and leaving little room for ambiguity regarding the study's methods and objectives.\n\nThe proposal is interesting. Although it is presented explicitly for RNN, the underlying principles and approaches have strong adaptability potential. The proposed sparse ternary orthogonal recurrent weights could be effectively applied across various domains (with necessary modifications for the new application domain).", "weaknesses": "My major concern with this paper is regarding the experimental section. Specifically, in lines 123 - 125, the authors claim: *\"Even with binarization, transformer models [...], making them unsuitable for tasks involving long-term dependencies on edge devices.\"* I find this assertion to be overly restrictive, as recent literature provides a substantial body of work on optimizing Transformers for edge devices and handling long-term dependencies, which is not discussed here. For example, numerous studies have been conducted on lightweight binary Transformers [1, 2, 3, 4] and approaches specifically designed to handle long-term dependencies [5, 6, 7].\nConsequently, the state-of-the-art section also appears narrow, as it overlooks several relevant studies and advancements in Transformer models that are critical to this discussion.\n\n[1] Liu, Z., Oguz, B., Pappu, A., Xiao, L., Yih, S., Li, M., ... & Mehdad, Y. (2022). BiT: Robustly Binarized Multi-distilled Transformer. Advances in Neural Information Processing Systems (NeurIPS), 35, 14303-14316.\n\n[2] He, Y., Lou, Z., Zhang, L., Liu, J., Wu, W., Zhou, H., & Zhuang, B. (2023). BiViT: Extremely Compressed Binary Vision Transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision (pp. 5651-5663).\n\n[3] Wang, Z., Luo, H., Xie, X., Wang, F., & Shi, G. (2024, March). BVT-IMA: Binary Vision Transformer with Information-Modified Attention. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 38, No. 14, pp. 15761-15769).\n\n[4] Gao, T., Xu, C. Z., Zhang, L., & Kong, H. (2024). GSB: Group superposition binarization for vision transformer with limited training samples. Neural Networks, 172, 106133.\n\n[5] Wu, H., Xu, J., Wang, J., & Long, M. (2021). Autoformer: Decomposition Transformers with Auto-Correlation for Long-Term Series Forecasting. Advances in Neural Information Processing Systems (NeurIPS), 34, 22419-22430.\n\n[6] Zhou, H., Zhang, S., Peng, J., Zhang, S., Li, J., Xiong, H., & Zhang, W. (2021, May). Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting. In Proceedings of the AAAI conference on artificial intelligence (Vol. 35, No. 12, pp. 11106-11115).\n\n[7] Zhou, T., Ma, Z., Wen, Q., Wang, X., Sun, L., & Jin, R. (2022, June). FEDformer: Frequency Enhanced Decomposed Transformer for Long-term Series Forecasting. In International conference on machine learning (pp. 27268-27286). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sgFUlaywBc", "reviewer": "Reviewer_wQjw", "summary": "This paper tackles the challenge of binarizing orthogonal recurrent neural networks (oRNNs), a problem that has been hindered by instability and inconsistency in previous formulations. The authors propose HadamRNN, a novel approach that utilizes Hadamard matrices to parameterize oRNNs with binary and sparse ternary weights. This method cleverly addresses the instability issues and offers a consistent framework for binarizing oRNNs. Furthermore, the paper introduces an optimized block version of HadamRNN, which brings about computational efficiency.", "questions": "At this point I am on the border with a leaning towards rejection but the following things might help along with other reviewers comments. \n\nThe paper presents a valuable contribution to the field of oRNNs by introducing a stable and efficient binarization method. However, the lack of real-world evaluation and potential concerns regarding training time and stability hinder its immediate acceptance. I encourage the authors to address these concerns by:\n\n1) Expanding the evaluation to include more diverse and realistic datasets. This would demonstrate the practical value of HadamRNN and provide a more comprehensive assessment of its capabilities.\n\n2) Providing a detailed analysis of training time and stability. This would offer valuable insights into the practical considerations of deploying HadamRNN in real-world applications.\n\nBy addressing these points, the authors can significantly strengthen the paper and increase its impact.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) Novel Approach: The introduction of Hadamard matrices for parameterization is a novel and effective way to address the instability issues associated with binarizing oRNNs.\n\n2) Theoretical Soundness: The paper provides a solid theoretical foundation for the proposed method and demonstrates its consistency.\n\n3) Performance: The empirical results on benchmark datasets (copy task, MNIST, IMDB) are promising, showing comparable performance to full-precision models. Notably, HadamRNN is the first binary recurrent weight model to handle the copy task over 1000 timesteps.\n\n4) Optimization: The optimized block version of HadamRNN offers improved computational efficiency.\n\n\n--------------------------------------\nAfter rebuttal:\n\nThe authors have addressed my concerns at length and added addiitonal experiments supporting the claims. I am in support of accepting the paper but might not be able to champion it.", "weaknesses": "At a high-level, while I appreciate the work towards making oRNNs work better and efficient, they themselves have quite a few issues including expressivity. \n\n1) Limited Real-World Applicability: While the benchmarks used are common in the literature, they often do not translate well to real-world scenarios. oRNNs, in general, have not seen widespread adoption in practical applications.\n\n2) Training Time: The authors mention FastGRNN (Kusupati et al., 2018), which suggests that training oRNN models can be significantly slower (an order of magnitude or more) compared to other methods. It would be beneficial to see a comparison of training times for the proposed HadamRNN models against relevant baselines. Additionally, a discussion on the stability of training these models would be valuable.\n\n3) Lack of Diverse Datasets: The evaluation primarily relies on toy datasets. To strengthen the claims and demonstrate broader applicability, it would be crucial to include more real-world datasets, even if smaller scale, such as those from the GLUE benchmark (e.g., SST-2, QQP) or SQUAD for question answering.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)