A Formal Hierarchy of RNN Architectures

Understand

We develop a formal hierarchy of the expressive capacity of RNN architectures.

• The hierarchy is based on two formal properties: space complexity, which measures the RNN's memory, and rational recurrence, defined as whether the recurrent update can be described by a weighted finite-state machine.
• We place several RNN variants within this hierarchy.
• For example, we prove the LSTM is not rational, which formally separates it from the related QRNN (Bradbury et al., 2016).