HADAMRNN: BINARY AND SPARSE TERNARY ORTHOGONAL RNNS

Authors: Armand Foucault, Francois Malgouyres, Franck Mamalet
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: Recurrent neural networks, quantization, orthogonal matrices, Hadamard matrices

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.

Decision: accept (poster)
Reviewer scores: 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1729282355469

thread_type:
official_review

<thread_object>
creator: reviewer_wqjw

<content>
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.

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.

2) Theoretical Soundness: The paper provides a solid theoretical foundation for the proposed method and demonstrates its consistency.

3) 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.

4) Optimization: The optimized block version of HadamRNN offers improved computational efficiency.


--------------------------------------
After rebuttal:

The 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. 

1) 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.

2) 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.

3) 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.

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. 

The 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:

1) 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.

2) 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.

By addressing these points, the authors can significantly strengthen the paper and increase its impact.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730556254279

thread_type:
official_review

<thread_object>
creator: reviewer_gcyv

<content>
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.

strengths:
The paper is well-organized and has a high level of clarity in its writing and the presentation of its proposal.

Each 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.

The 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].
Consequently, 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.

[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.

[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).

[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).

[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.

[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.

[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).

[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.

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.

Based 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.

Other 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730581611013

thread_type:
official_review

<thread_object>
creator: reviewer_fwft

<content>
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.

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. 

The 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 .
The 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.

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?

- 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.

- 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732469677152

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Overall reply to the reviewers

comment:
We would like to thank all the reviewers for their time spent reading the article, as well as for their positive comments and constructive criticism, which have greatly contributed to improving the quality of our work.

For each reviewer, we provide point-by-point responses to the issues raised in their report. The reviewers' comments are highlighted in bold, while our responses are in regular text. Below, we summarize the changes we will implement based on the reviewers' feedback.

The revised version of the article will be submitted by November 26.

Below, we summarize the modifications.

- Major modifications:
    - We provide a new appendix that describes the STE and presents an example of the recurrent weight matrix for $d_h=4$.
    - In addition to Tables 2 and 3, we illustrate the benefits of using HadamRNN and Block-HadamRNN through plots in a new appendix.
    - We provide an expanded bibliography on transformers that handle long-term dependencies. %and quantized transformers.
      
    - We include new benchmarks:
        - SST-2 and (if time permits) CoLA from GLUE.
        - HAR-2 and DSA-19, benchmarks for human activity recognition (from the FastGRNN article).
        - Time permitting, Yelp-5, a sentiment analysis benchmark (from the FastGRNN article).
    - We provide a comparison with binary transformers on the above GLUE benchmarks.
    - We provide the training times and a stability analysis.
- Minor modifications:
    - We list additional potential applications of Hadamard matrices in the conclusion.
    - We have proofread the article to eliminate any remaining typos.
    - We have labeled the axes of the plot in Figure 1.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732707174409

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Revised paper submitted

comment:
Dear reviewers and area chair,

We have uploaded the updated version of the article.

All changes are highlighted in red.

In comparison to the previously announced updates, we have made the following modifications:
    
1. The additional benchmarks are:
   - SST-2 and QQP from GLUE, with a comparison to all existing quantized BERT models addressing these benchmarks. 
    - The IoT tasks HAR-2 and DSA-19 from FastGRNN.
2. We have included only the bibliography on quantized LLMs in Section 2, and we believe it is comprehensive. It is complemented by the comparison outlined above. The reasons for not including a bibliography on transformers handling long-term dependencies will be clear from the current content of Section 2.
3. There are a few modifications aimed at saving space. These are not highlighted in red and do not alter the meaning of the text.

All other modifications are as described in our previous posts.

Thank you very much for all your feedback. It has helped us improve our article.

Best regards,

The authors.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733152207851

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Feedback

comment:
Dear reviewers,
The end of the discussion period is approaching.
We would be very grateful for your feedback on the revised version.

Sincerely yours,
The authors.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper presents a method to parameterize orthogonal RNNs with binary and sparse ternary weights using Hadamard matrices. This approach, including HadamRNN and Block-HadamRNN, resolves previous instability issues and achieves performance close to full-precision models. The reviewers are divided about this work. On one hand, this was not done previously, but on the other hand the experiments are weak with not diverse experiments and no clear path to real-world applicability. While the paper's outcome is less certain than other cases, it presents a promising new concept that warrants exposure to the ICLR audience. Therefore, I do recommend acceptance.