Abstract
Recurrent Neural Networks (RNNs) are highly efficient for online sequence processing but suffer from significant training bottlenecks due to the sequential nature of Backpropagation Through Time (BPTT). This paper introduces Diagonal State Feedbacks (DSF), a novel training method that approximates gradients by assuming a stationary, diagonal feedback matrix. By transforming the backward pass into a Linear Time Invariant (LTI) system, DSF enables parallelization via Fast Fourier Transforms (FFT) or prefix-sums. This shift reduces sequential complexity from $\mathcal{O}(T)$ to $\mathcal{O}(\log T)$, allowing RNNs to achieve training scalability comparable to Transformers and State-Space Models (SSMs) while maintaining competitive performance on language modeling benchmarks.
Introduction
While Transformers have become the dominant architecture for sequence modeling due to their parallelizable training, RNNs remain superior for low-latency, memory-efficient inference. The primary obstacle to scaling RNNs is BPTT, which requires sequential gradient computation across time steps. This paper addresses this limitation by proposing DSF, which replaces the time-varying Jacobian matrices in BPTT with a fixed, diagonal feedback matrix. This approximation allows for massive parallelization on modern hardware, bridging the gap between recurrent architectures and highly parallelizable models like Transformers.
Methodology: Diagonal State Feedbacks
The core innovation of DSF lies in the simplification of the gradient flow. In standard BPTT, the Jacobian matrix—representing how the hidden state changes—is unique at every time step, necessitating sequential computation. DSF introduces two key modifications:
- Stationarity: The method assumes the feedback is time-invariant, using a single fixed matrix ($A$) throughout the sequence.
- Diagonality: By restricting this matrix to be diagonal, the backward pass effectively becomes an LTI system that can be solved in parallel.
Complexity and Parallelization
By utilizing the Fast Fourier Transform (FFT) or prefix-sum algorithms, DSF calculates gradients for all time steps simultaneously. As shown in the table below, this reduces the sequentiality of the training process from linear to logarithmic time relative to the sequence length $T$.
Experimental Results
The authors evaluated DSF on the Penn Treebank (PTB) and Wikitext-103 datasets to assess its performance and scalability.
- Performance: On Wikitext-103, DSF-trained RNNs achieved a validation perplexity of 31.54, closely trailing the 28.32 achieved by full BPTT. Notably, DSF significantly outperformed "Fully Truncated BPTT" (FT-BPTT), which ignores temporal gradients, indicating that the stationary feedback successfully captures long-range dependencies.
- Comparison with SSMs: Under similar parameter constraints, DSF-trained RNNs outperformed modern State-Space Models, such as the EMA layer from MEGA (31.54 vs. 33.19 perplexity).
- Scalability: The performance gap between DSF and BPTT remained stable as model dimensions increased from 128 to 1024, suggesting that the approximation holds well for large-scale applications.
Discussion and Conclusion
DSF demonstrates that mathematically exact gradients are not a prerequisite for effective RNN training. A stationary, diagonal approximation provides a sufficient signal for learning while unlocking significant computational efficiencies.
Future research directions include exploring more principled initialization strategies for the diagonal matrix $A$ (potentially drawing from HiPPO or S4 frameworks) and investigating adaptive feedback mechanisms that could further narrow the performance gap with BPTT without sacrificing parallelization benefits. By enabling faster training, DSF revitalizes the RNN architecture for large-scale sequence modeling tasks.
Summary updated