Recurrent Networks as State Machines

A recurrent network receives an input at one step, combines it with the previous hidden state, and produces a new state. The same transition parameters are reused across the sequence. The state has fixed width. So it cannot preserve every detail indefinitely. Training decides which information is compressed, overwritten, or allowed to influence later outputs.

Machine translation put a size on that summary in 2014. The method was “a multilayered Long Short-Term Memory (LSTM) to map the input sequence to a vector of a fixed dimensionality, and then another deep LSTM to decode the target sequence from the vector”. Sutskever and colleagues give the width exactly: “deep LSTMs with 4 layers, with 1000 cells at each layer and 1000 dimensional word embeddings, with an input vocabulary of 160,000 and an output vocabulary of 80,000”. That model reached a BLEU score of 34.8 on the WMT-14 English-to-French test set. The phrase-based statistical baseline reached 33.3. Long sentence or short, the same fixed width carried it.

Two years later the same idea was scaled and put into service. Google's 2016 translation system is a deep LSTM network with 8 encoder and 8 decoder layers, using attention and residual connections. That is twice the depth of the 2014 model on each side, in a paper with 31 authors. The abstract says what the depth bought: “Using a human side-by-side evaluation on a set of isolated simple sentences, it reduces translation errors by an average of 60% compared to Google's phrase-based production system.” Then it shipped. The product announcement of 15 November 2016 records eight language pairs, and Barak Turovsky wrote in it that “These represent the native languages of around one-third of the world's population, covering more than 35% of all Google Translate queries!” A compact learned state was not a laboratory curiosity. It was already carrying more than a third of a production translation service.

Unrolling shows repeated computation, not separately parameterized layers. The transition sized above at 1000 cells per layer is the one transition, applied again at every step of the sequence. The picture below is one cell drawn many times, not many cells.

The state transition can support several task interfaces. Two of these layouts have a documented failure point. Both were named in print rather than inferred.

Sequence-to-sequence puts the entire source into one vector before decoding begins. That vector is the limit. The 2014 paper that introduced attention said so in its own abstract: “we conjecture that the use of a fixed-length vector is a bottleneck in improving the performance of this basic encoder-decoder architecture”. A companion paper the same year measured the cost: “We show that the neural machine translation performs relatively well on short sentences without unknown words, but its performance degrades rapidly as the length of the sentence and the number of unknown words increase.” That is why attention belongs in this column. It does not make the summary better. It removes the requirement that there be only one.

Autoregressive generation fails differently, and its failure is a training-time decision rather than a capacity limit. The model is trained on the true previous token. At inference it is fed its own. Scheduled sampling, from Google in 2015, states the consequence in its abstract: “This discrepancy between training and inference can yield errors that can accumulate quickly along the generated sequence.” Facebook AI Research reached the same diagnosis separately, in a paper posted on 20 November 2015: “However, at test time the model is expected to generate the entire sequence from scratch. This discrepancy makes generation brittle, as errors may accumulate along the way.” Two labs, two months apart, describing the same accumulation.

Recurrence is still useful when streaming, latency, or irregular lengths matter. The on-device speech case is not a design principle but a shipped product with published numbers. Google's RNN-Transducer for phones, described in 2018, has an encoder of eight layers of uni-directional LSTM cells. Each layer has 2,048 hidden units followed by a 640-dimensional projection layer. The prediction network is 2 LSTM layers with the same sizes. Nothing in that stack may read a frame that has not arrived.

The deployment budget is where the compact state earns its place. The trained model was 450MB. Quantization gave a 4x compression and a 4x speedup at run-time. Google's launch post of 12 March 2019 gives the end of that arithmetic: “After compression, the final model is 80MB.” The shipped model runs faster than real time on a single core, offline.

Separate state-interface errors from optimization and data failures. The last step, benchmarking streaming cost, is worth doing with a prior about what it will find. Sequential execution is the constraint, and Attention Is All You Need named it in its introduction in 2017: “This inherently sequential nature precludes parallelization within training examples, which becomes critical at longer sequence lengths, as memory constraints limit batching across examples.”

Removing that constraint was worth measuring, and in 2018 it was measured. The Simple Recurrent Unit paper reports that “SRU achieves 5—9x speed-up over cuDNN-optimized LSTM on classification and question answering datasets”. The comparison is against a cuDNN-optimized LSTM, not a naive one. So the gap is not an implementation defect to be tuned away. Per-step overhead and state management are the terms a parallelizable state deletes. Total arithmetic is not where the difference lives.

A bidirectional encoder processes the sequence in both directions and combines the two representations. It is appropriate when the entire input is available before prediction. The gain is real and it has a size. On TIMIT framewise phoneme classification in 2005, Graves and Schmidhuber measured test-set accuracy of 70.2% for retrained BLSTM and 69.8% for BLSTM. A unidirectional LSTM reached 66.0% with a 5-frame target delay and 64.6% with no delay.

The same paper refuses the architecture for online work: “For the first class of problems BRNNs are useless, since meaningful outputs are only available after the net has run backwards.” Eleven years later Baidu's Deep Speech 2 gave the deployment consequence in almost the same terms: “Bidirectional RNN models are challenging to deploy in an online, low-latency setting, because they are built to operate on an entire sample, and so it is not possible to perform the transcription process as the utterance streams from the user.” Their answer was not to keep the future observations. It was a lookahead convolution layer, also called row convolution, that lets a unidirectional stack match the bidirectional one.

So bidirectionality is not a free upgrade for streaming systems. Using future observations during offline evaluation creates leakage if production must decide before those observations exist. The several points of framewise accuracy it appears to add are points the deployed system will not have.