Recurrent neural networks (RNNs) are widely used to model sequential data but
 their non-linear dependencies between sequence elements prevent parallelizing
 training over sequence length. We show the training of RNNs with only linear
 sequential dependencies can be parallelized over the sequence length using the
 parallel scan algorithm, leading to rapid training on long sequences even with
 small minibatch size. We develop a parallel linear recurrence CUDA kernel and
 show that it can be applied to immediately speed up training and inference of
 several state of the art RNN architectures by up to 9x.  We abstract recent work
 on linear RNNs into a new framework of linear surrogate RNNs and develop a
 linear surrogate model for the long short-term memory unit, the GILR-LSTM, that
 utilizes parallel linear recurrence.  We extend sequence learning to new
 extremely long sequence regimes that were previously out of reach by
 successfully training a GILR-LSTM on a synthetic sequence classification task
 with a one million timestep dependency.
 Recurrent neural networks (RNNs) are widely used for sequence modelling tasks in domains such as natural language processing BID17 , speech recognition BID1 , and reinforcement learning BID9 . Most RNNs, including popular variants such as long short-term memories (LSTMs), introduced by BID10 , and gated recurrent units (GRUs), introduced by BID5 , contain a non-linear dependency between sequential inputs. These non-linear dependencies create a very flexible class of models but limit the feasibility of training RNNs on long sequences as each sequence element must be processed sequentially. Modelling sequences of thousands to millions of elements is important to domains such as robotics, remote sensing, control systems, speech recognition, medicine, and finance.The RNN serial evaluation inefficiency problem is usually mitigated by parallelizing the forward and backward pass over a minibatch of inputs. Without minibatches, RNN evaluation is a sequence of matrix-vector multiplications. Minibatches transform RNN computation into a sequence of more efficient matrix-matrix multiplications, but this speed-up brings several disadvantages. RNN model size is often limited by GPU memory size, and running a forward and backward pass on a minibatch requires memory linear in the minibatch size. Grouping data into minibatches increases the latency of each pass and reduces the rate of optimization steps. Finally, training with larger minibatches damages generalization ability BID12 . Given these effects, it is desirable to obtain high training throughput with small minibatches. Persistent RNNs BID6 ) use a novel implementation that can achieve high GPU utilization with very small minibatch sizes when the recurrent state is larger than 500 elements, but even persistent RNNs become limited by the serial evaluation inefficiency at smaller hidden sizes.Numerous prior works have shown strong performance from neural sequential models with only linear dependence on earlier sequence elements. BID2 investigated RNNs with only elementwise linear recurrence relations h t = α t h t−1 + (1 − α t ) x t and developed linear variants of LSTM and GRU that perform similarly to standard non-linear RNNs on text generation tasks. BID4 , , BID7 , and van den have successfully applied networks of convolutions over sequences for tasks such as machine translation, language modelling, and audio generation. These works have observed up to an order of magnitude increase in training throughput compared to RNN alternatives. Convolutional sequence models typically rely on either an attention mechanism or a (possibly linear) recurrent layer to integrate information at scales larger than the filter width. Introduction of a recurrent layer prevents full parallelization over the sequence length while attention mechanisms are expensive to apply on long sequences in online inference use cases.A linear recurrence is a specific instance of a general form of computation known as a scan. Scans and reductions are computations involving repeated application of a binary operator ⊕ over an array of data. Computing the sum or maximum of an array is an example of a reduction, while a cumulative sum is a common example of a scan operation. Throughout this work, the scan of ⊕ with initial value b is defined as DISPLAYFORM0 The reduction of ⊕ over array A and initial value b is denoted REDUCE(⊕, A, b) and is the final element of SCAN(⊕, A, b). Despite their dependent computation graph, algorithms exist to parallelize scans and reductions when ⊕ is associative BID14 . BID3 shows that first order recurrences of the form h t = (Λ t ⊗ h t−1 ) ⊕ x t can be parallelized with the parallel scan algorithm if three conditions are met: DISPLAYFORM1 Considering the familiar operations in linear algebra, we see that the associative operation of vector addition (x ⊕ y = x + y), the semiassociative operation of matrix-vector multiplication (A ⊗ x = Ax) and the associative operation of matrix-matrix multiplication (A B = AB) satisfy Blelloch's three conditions, allowing h t = Λ t h t−1 + x t to be evaluated in parallel over time steps t for vectors x t and square matrices Λ t .We investigate this idea further and deliver the following contributions:• We classify RNNs which satisfy the conditions above, and show that many RNNs used in practice such as the Quasi-RNNs (QRNNs) introduced by BID4 are contained in this class.• We provide an implementation of the parallel linear recurrence algorithm as a CUDA kernel, and show that it speeds up training of QRNN and BID19 's Simple Recurrent Unit (SRU) architectures by factors of up to 9x.• We describe how several recent linear RNNs can be described as linear surrogates for non-linear architectures. We introduce a linear surrogate for the LSTM and show that we are able to train it with a speedup of 5-10x compared to the CuDNN LSTM when we use the parallel linear recurrence algorithm. A significant portion of the success of deep learning can be attributed to access to massive amounts of computation. Most of this computation is accessed through two highly efficient and parallelizable building blocks: matrix multiplication and convolution. Recent research has demonstrated that linear RNNs can achieve similar prediction accuracy to non-linear RNNs on a wide variety of tasks in a fraction of the training time. We propose the framework of LS-RNNs as a way to tame the growing zoo of sequential neural nets. We identify linear recurrence as another parallelizable building block for current and future sequential models and we use it to obtain significant speedups on already fast models. With the power of parallel linear recurrence we are able to solve a sequential dependency problem multiple orders of magnitude larger than anything done prior. Future applications of parallel linear recurrence within neural nets could include parallel training of memory augmented models or providing a new sort of image filter on very high resolution images. We hope that parallel linear recurrence can be to large scale sequence modelling what fast convolution algorithms are to image recognition.
use parallel scan to parallelize linear recurrent neural nets. train model on length 1 million dependency Proposes accelerating RNN by applying the method from Blelloch. The authors propose a parallel algorithm for Linear Surrogate RNNs, which produces speedups over the existing implements of Quasi-RNN, SRU, and LSTM.