Advancing Regular Language Reasoning in Linear Recurrent Neural Networks

Ting-Han Fan, Ta-Chung Chi, Alexander I. Rudnicky

Abstract

In recent studies, linear recurrent neural networks (LRNNs) have achieved Transformer-level performance in natural language modeling and long-range modeling while offering rapid parallel training and constant inference costs. With the resurged interest in LRNNs, we study whether they can learn the hidden rules in training sequences, such as the grammatical structures of regular language. We theoretically analyze some existing LRNNs and discover their limitations on regular language. Motivated by the analysis, we propose a new LRNN equipped with a block-diagonal and input-dependent transition matrix. Experiments suggest that the proposed model is the only LRNN that can perform length extrapolation on regular language tasks such as Sum, Even Pair, and Modular Arithmetic.

Introduction

Linear Recurrent Neural Networks (LRNNs)—including architectures like S4, S4D, and RWKV—have emerged as powerful competitors to Transformers by combining the parallel training efficiency of CNNs with the constant-time inference of RNNs. However, a fundamental question persists: do these models truly "understand" the underlying rules of the sequences they process?

This study focuses on regular languages, the simplest tier of the Chomsky hierarchy recognizable by Finite State Automata (FSA). A model that masters a regular language should exhibit length extrapolation: the ability to apply rules learned on short sequences (e.g., length 40) to much longer ones (e.g., length 500). The researchers discovered that most existing LRNNs fail this test, proving that input-independent or purely diagonal models are mathematically inconsistent when trying to represent basic operations like subtraction.

Methodology

To overcome these limitations, the authors propose a new LRNN architecture designed to simulate Finite State Automata. The architecture incorporates several key innovations:

  1. Input-Dependent Transitions: Unlike standard LRNNs with fixed transition matrices, the proposed model uses $A_k = g(u_k)$, allowing the transition to change at every timestep based on the input.
  2. Block-Diagonal Structure: By moving beyond simple diagonal matrices to a block-diagonal structure, the model gains the expressiveness needed for complex state interactions, such as rotations or permutations.
  3. Stability via $p$-norm Constraints: To prevent numerical instability in long sequences, the authors enforce a $p$-norm constraint (specifically $p=1.2$) on the transition blocks.
  4. Parallel Scan (PScan): To maintain computational efficiency, the recurrence is implemented using a Parallel Scan algorithm, enabling $O(\log L)$ training time.
Computational graph of the proposed LRNN architecture utilizing a parallel scan for efficient training.

Experimental Results

The models were evaluated on three synthetic regular language tasks: Sum(M), EvenPair(M), and ModArith(M). The primary challenge was length extrapolation, where models were trained on sequences of length 40 and tested on sequences of length 500.

As shown in the results below, the proposed model was the only architecture capable of successful extrapolation. On the Sum(5) and ModArith(5) tasks, it achieved near-perfect accuracy, while baselines like S4 and S4D failed to perform significantly better than random guessing (approximately 27% accuracy).

Accuracy comparison of the proposed model versus LRNN baselines on length extrapolation tasks.

Conclusion

This research identifies a critical gap in the reasoning capabilities of existing LRNNs and provides a theoretically grounded solution. By employing input-dependent, block-diagonal transition matrices, the proposed model successfully bridges the gap between neural networks and the symbolic reasoning required for regular languages. While this work focuses on regular languages, it provides a foundation for extending LRNN capabilities to more complex linguistic structures and formal logic.

Summary updated

Abstract

In recent studies, linear recurrent neural networks (LRNNs) have achieved Transformer-level performance in natural language modeling and long-range modeling while offering rapid parallel training and constant inference costs. With the resurged interest in LRNNs, we study whether they can learn the hidden rules in training sequences, such as the grammatical structures of regular language. We theoretically analyze some existing LRNNs and discover their limitations on regular language. Motivated by the analysis, we propose a new LRNN equipped with a block-diagonal and input-dependent transition matrix. Experiments suggest that the proposed model is the only LRNN that can perform length extrapolation on regular language tasks such as Sum, Even Pair, and Modular Arithmetic.
BibTeX
@inproceedings{fan2024advancing,
  author = {Ting-Han Fan and Ta-Chung Chi and Alexander I. Rudnicky},
  title = {{Advancing Regular Language Reasoning in Linear Recurrent Neural Networks}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2024},
  url = {https://openreview.net/forum?id=gsKtJtFZJe},
}
Figure