Parallel Recursive LSTM

• URL: http://arxiv.org/abs/2605.17108v1
• Date: Sat, 16 May 2026 18:28:59 GMT
• Title: Parallel Recursive LSTM
• Abstract summary: We introduce the Parallel Recursive LSTM, a hierarchical recurrent architecture that replaces left-to-right recurrence with nonlinear state composition over a balanced computation tree.<n>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.
• Score: 26.883902799977964
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Latent Recurrent Transformer: Architecture Exploration, Training Strategies, and Scaling Behavior [107.2098567818173]
  Latent Recurrent Transformer (LRT) is a lightweight augmentation of autoregressive transformers.<n>LRT reuses a high-level source-layer hidden state from the previous token as recurrent memory for the next token.
  arXiv  Detail & Related papers  (2026-05-26T10:10:26Z)
• A Muon-Accelerated Algorithm for Low Separation Rank Tensor Generalized Linear Models [9.341971485553428]
  Low Separation Rank (LSR) decompositions reduce model complexity by imposing low-rank multilinear coefficient tensor tensor.<n>A representative approach for estimating LSR-based tensor GLMs (LSR-TGLMs) is the Low Separation Rank Regression (LSRTR) algorithm, which adopts block coordinate descent and enforces naivesity of the factor through repeated QR-based projections.<n>We propose LSRTR-M, which incorporates Muon updates into the LSRTR framework. Specifically, LSRTR-M preserves the original block coordinate scheme while replacing the projection-based factor updates with Muon steps.
  arXiv  Detail & Related papers  (2026-04-06T14:47:46Z)
• Improved state mixing in higher-order and block diagonal linear recurrent networks [16.116191916700554]
  Linear recurrent networks (LRNNs) and linear state space models (SSMs) promise computational and memory efficiency on long-sequence modeling tasks.<n>Dense and nonlinear architectures (e.g., LSTMs) on the other hand are provably more expressive, but computationally costly.<n>Here, we explore how expressivity in LRNNs can be increased via richer state mixing across time and channels while maintaining competitive efficiency.
  arXiv  Detail & Related papers  (2026-02-12T14:51:59Z)
• PRISM: Parallel Residual Iterative Sequence Model [52.26239951489612]
  We propose PRISM (Parallel Residual Iterative Sequence Model) to resolve this tension.<n>PRISM introduces a solver-inspired inductive bias that captures key structural properties of multi-step refinement in a parallelizable form.<n>We prove that this formulation achieves Rank-$L$ accumulation, structurally expanding the update manifold beyond the single-step Rank-$1$ bottleneck.
  arXiv  Detail & Related papers  (2026-02-11T12:39:41Z)
• Parallelizable memory recurrent units [1.3159512679346688]
  We introduce a new family of RNNs, the memory recurrent units (MRUs), that combine the persistent memory capabilities of nonlinear RNNs with the parallelizable computations of SSMs.<n>We show that BMRU achieves good results in tasks with long-term dependencies, and can be combined with state-space models to create hybrid networks that are parallelizable and have transient dynamics as well as persistent memory.
  arXiv  Detail & Related papers  (2026-01-14T14:01:11Z)
• ParaRNN: Unlocking Parallel Training of Nonlinear RNNs for Large Language Models [9.107447466062409]
  ParaRNN is a framework that breaks the sequence-parallelization barrier for nonlinear RNNs.<n>Our implementation achieves speedups of up to 665x over sequential application.<n>ParaRNN is released as an open-source framework for automatic training-parallelization of nonlinear RNNs.
  arXiv  Detail & Related papers  (2025-10-24T13:28:33Z)
• Sequential-Parallel Duality in Prefix Scannable Models [68.39855814099997]
  Recent developments have given rise to various models, such as Gated Linear Attention (GLA) and Mamba.<n>This raises a natural question: can we characterize the full class of neural sequence models that support near-constant-time parallel evaluation and linear-time, constant-space sequential inference?
  arXiv  Detail & Related papers  (2025-06-12T17:32:02Z)
• DeltaProduct: Improving State-Tracking in Linear RNNs via Householder Products [60.72655477351486]
  Linear Recurrent Neural Networks (linear RNNs) have emerged as competitive alternatives to Transformers for sequence modeling.<n>Existing architectures face a fundamental trade-off between expressivity and efficiency, dictated by the structure of their state-transition matrices.
  arXiv  Detail & Related papers  (2025-02-14T16:59:05Z)
• RWKV: Reinventing RNNs for the Transformer Era [54.716108899349614]
  We propose a novel model architecture that combines the efficient parallelizable training of transformers with the efficient inference of RNNs. We scale our models as large as 14 billion parameters, by far the largest dense RNN ever trained, and find RWKV performs on par with similarly sized Transformers.
  arXiv  Detail & Related papers  (2023-05-22T13:57:41Z)
• Accelerating Feedforward Computation via Parallel Nonlinear Equation Solving [106.63673243937492]
  Feedforward computation, such as evaluating a neural network or sampling from an autoregressive model, is ubiquitous in machine learning. We frame the task of feedforward computation as solving a system of nonlinear equations. We then propose to find the solution using a Jacobi or Gauss-Seidel fixed-point method, as well as hybrid methods of both. Our method is guaranteed to give exactly the same values as the original feedforward computation with a reduced (or equal) number of parallelizable iterations, and hence reduced time given sufficient parallel computing power.
  arXiv  Detail & Related papers  (2020-02-10T10:11:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.