Metric Automata Theory: A Theory of Recurrent Neural Networks
Adam Dankowiakowski, Alessandro Ronca
We propose Metric Automata Theory, an elegant generalisation of classic Automata Theory to continuous dynamical systems, that constitutes a unifying theory of all kinds of Recurrent Neural Networks (RNNs), including widely-adopted architectures such as xLSTM and State Space Models (SSMs). The theory allows one to analyse RNNs both in the finite and unbounded precision settings seamlessly, and to use the fundamental results of Automata Theory. It also provides a novel notion of robustness that guarantees numerical stability, contributes to stability of learning, and notably allows one to prove results for real-world finite-precision implementations while abstracting away the difficulties introduced by finite-precision arithmetic.We employ the theory to prove a comprehensive set of expressivity results for widely-adopted recurrent neural architectures, with a focus on robustness and finite-precision. Notably, we prove that xLSTM, based on non-linear recurrence, is capable of recognising all star-free regular languages robustly, and hence by our theory it can also do so under any floating-point implementation given sufficient precision. Furthermore, we prove that linear recurrence, characterising SSMs, is not sufficient to robustly recognise all star-free languages. This provides a potential explanation for why xLSTM shows superior performance to SSMs on several tasks, and it gives a novel perspective on the importance of non-linear recurrences.We provide an improved understanding of the capabilities of Mamba, a popular SSM model. We show that Mamba is not generally capable of recognising the star-free languages under finite-precision, which is seemingly in contrast with the existing expressivity results for SSMs and also with its good empirical performance. We clarify the picture, by showing that Mamba admits a piecewise-linearly separable state space that allows it to approximate star-free languages, with some length-generalisation abilities. At the same time, Mamba does not admit such state spaces for languages like Parity. This explains why empirically Mamba performs well on star-free languages, and fails on Parity.