Parallel Recursive LSTM
For researchers working on efficient sequence modeling, PR-LSTM offers a way to parallelize recurrent computation without sacrificing nonlinear state-tracking capabilities, addressing a key bottleneck in long-context settings.
The paper introduces the Parallel Recursive LSTM (PR-LSTM), a hierarchical recurrent architecture that replaces sequential recurrence with recursive nonlinear state composition over a balanced tree, reducing parallel depth from linear to logarithmic while retaining nonlinear gated states. Empirically, PR-LSTM achieves strong generalization on formal-language benchmarks, solving more tasks than RNN, LSTM, and Transformer baselines, and avoids quadratic attention scaling.
Transformers have become the dominant architecture for sequence modeling by using self-attention to enable expressive and highly parallel processing. However, the resulting quadratic time and memory costs limit efficiency in long-context settings. Recurrent models such as LSTMs provide explicit nonlinear state updates and strong state-tracking capabilities, yet their strictly sequential computation limits parallelism. We introduce the Parallel Recursive LSTM (PR-LSTM), a hierarchical recurrent architecture that replaces left-to-right recurrence with recursive nonlinear state composition over a balanced computation tree. Tokens are first mapped independently to latent states, which are then recursively merged by a learned gated composition block. This structure uses the reduction pattern underlying parallel scans as a fixed execution schedule, rather than assuming an associative recurrence. As a result, PR-LSTM retains nonlinear gated state representations while reducing recurrent parallel depth from linear to logarithmic. Empirically, PR-LSTM achieves strong sequence-length generalization on formal-language benchmarks, solving more tasks than standard RNN, LSTM, and Transformer baselines, while avoiding the quadratic scaling of attention. These results suggest that recurrent computation can be reorganized hierarchically to expose parallelism without restricting the transition dynamics to linear or associative forms.