Advancing Regular Language Reasoning in Linear Recurrent Neural Networks (2024)

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 .

## introduction there is a recent surge in the use of lrnns @xcite @xcite as alternatives to the de-facto transformer architecture @xcite , which is ingrained in the field of natural language processing. lrnns depart from the inter-timestep non-linearity design principle of classic rnns @xcite @xcite , while at the same time: 1. achieving transformer-level performance on the task of natural language modeling @xcite and even better performance on synthetic long-range modeling tasks @xcite @xcite @xcite . 2. having the added benefits of fast parallelizable training @xcite and constant inference cost. ## limitations of most lrnns in this section, we theoretically show that most lrnns are unable to represent arithmetic operations. the analysis serves as a motivation to study input-dependent transition matrices with constraints on their column norm. ## proposed method now that input-independent lrnns struggle with representing arithmetic operations, we review the paradigms known to model regular language, which is the type of formal language recognized by a finite state automata (fsa) @xcite ). an fsa is described by a 5-tuple (q, σ, δ, q 0 , f ). q and σ are non-empty sets of states and input symbols. q 0 ∈ q is an initial state. δ : q × σ → q is an input-dependent transition function; f ⊆ q is a set of final states. we hypothesize that an lrnn could model regular language if it can simulate an fsa, whose transition function has the following two key properties: ## conclusion in this work, we explored lrnns in the realm of regular language modeling. we discovered that existing lrnns cannot effectively represent subtraction. consequently, we proposed a new lrnn equipped with a block-diagonal and inputdependent transition matrix. our experiments confirmed the proposed model's capability to model various regular language tasks, including sum, even pair, and modular arithmetic, under the challenging length extrapolation setting.