Advancing Regular Language Reasoning in Linear Recurrent Neural Networks

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

Abstract

In recent studies, linear recurrent neural networks (LRNNs) have achieved Transformer-level performance in natural language and long-range modeling, while offering rapid parallel training and constant inference cost. With the resurgence of 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 in modeling regular language. Motivated by this 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 capable of performing length extrapolation on regular language tasks such as Sum, Even Pair, and Modular Arithmetic. The code is released at https://github.com/tinghanf/RegluarLRNN.

1. Introduction

While LRNNs like S4 and RWKV scale linearly with sequence length, it is unclear if they truly "reason" by learning the underlying rules of a language or merely memorize patterns. A robust model should learn the Finite State Automaton (FSA) governing a regular language, enabling it to generalize to sequences much longer than those seen during training. Current LRNNs often fail this "length extrapolation" test, relying on spurious shortcuts that collapse when sequence lengths increase. We identify that a primary cause is the mathematical inability of standard LRNNs—those with input-independent or purely diagonal transition matrices—to represent non-commutative operations like subtraction.

2. Methodology: Input-Dependent LRNNs

To overcome these limitations, we introduce an expressive architecture centered on input-dependent transition matrices. In our model, the transition matrix $A_k$ is a function of the current input $u_k$, allowing the internal state logic to adapt dynamically.

To maintain computational efficiency and stability, we employ several key techniques:

  • Block-Diagonal Structure: Transition matrices are organized into blocks to reduce parameter count while maintaining expressivity.
  • Stability via p-norm Constraints: We enforce a constraint on the column norms of transition blocks (using a p-norm where $p \approx 1.2$) to prevent gradient explosion over long sequences.
  • Parallel Scan (PScan): To preserve the $O(\log L)$ training efficiency of LRNNs, we utilize a parallel scan algorithm for the recurrence.
The proposed parallel scan architecture utilizes input-dependent transition matrices $A_k$ to dynamically update hidden states.

3. Experimental Evaluation

We evaluated our model against baselines (S4, S4D, and Liquid-S4) on three transduction tasks: Sum(M), EvenPair(M) (requiring long-term memory), and ModArith(M) (involving operator precedence and subtraction). Models were trained on short sequences (approx. 40 tokens) and tested on long sequences (approx. 500 tokens) to assess length extrapolation.

3.1 Results

Our model significantly outperformed all baselines in length extrapolation. While baseline models achieved high accuracy on short training sequences, their performance dropped to near-random levels on longer test sequences, indicating they failed to learn the actual rules. In contrast, our model achieved near-perfect accuracy across all tasks.

Comparison of accuracy on length extrapolation tasks. Our model maintains near-perfect performance while baselines fail to generalize.

On the complex ModArith(5) task, our model achieved 1.00 accuracy on length-500 sequences, whereas baselines hovered around 0.27, which is equivalent to random guessing. Furthermore, our PScan implementation remained efficient, training approximately 1.5x faster than standard sequential implementations.

4. Conclusion

This work highlights a fundamental limitation in current LRNNs regarding regular language reasoning. By introducing input-dependent, block-diagonal transition matrices and stabilizing them with p-norm constraints, we enable LRNNs to simulate FSAs and master length extrapolation. Future work will explore applying these architectural enhancements to large-scale natural language modeling, where similar reasoning capabilities are essential for robust performance.

Summary updated

Abstract

In recent studies, linear recurrent neural networks (LRNNs) have achieved Transformer-level performance in natural language and long-range modeling, while offering rapid parallel training and constant inference cost. With the resurgence of 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 in modeling regular language. Motivated by this 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 capable of performing length extrapolation on regular language tasks such as Sum, Even Pair, and Modular Arithmetic. The code is released at https://github.com/tinghanf/RegluarLRNN.
BibTeX
@inproceedings{fan2024advancing,
  author = {Ting-Han Fan and Ta-Chung Chi and Alexander 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