TL;DR
This paper introduces Metric Automata Theory (MAT), a novel mathematical framework that bridges the gap between discrete computer science (Automata Theory) and continuous deep learning (RNNs and State Space Models). By formalizing notions of "finite precision" and "robustness," the authors prove why non-linear models like xLSTM are fundamentally more capable of stable logic than linear models like Mamba, while also explaining Mamba's surprising empirical success through a new lens of geometric approximation.
The Expressivity Gap: Automata vs. Dynamical Systems
For decades, sequence processing has been described using two distinct languages: Automata Theory for discrete logic (like compilers or regular expressions) and Dynamical Systems for neural networks (RNNs, SSMs).
The core problem is that neural networks operate in a continuous state space with finite precision (floating-point math), making it difficult to apply classic discrete proofs to them. Previous attempts to bridge this gap often assumed infinite precision or ignored numerical stability. This paper tackles the "expressivity gap": Why do some models like Mamba struggle with simple logic tasks like "Parity" or "FLIP-FLOP" over long sequences, while others like xLSTM succeed? The authors provide a principled way to compare these wildly different architectures under realistic, finite-precision conditions.
Methods: Metric Automata Theory (MAT)
The authors propose MAT using several novel concepts to map continuous spaces to discrete logic:
- $\eta$-finiteness: Instead of counting discrete states, MAT looks at "components" of a continuous space. If a state space can be partitioned into a finite number of compact, path-connected "clumps," it is considered $\eta$-finite. This elegantly models how a neural network "discretizes" its continuous values into logical states.
- Robustness: A system is defined as robust if small perturbations (like floating-point rounding errors) don't push the state into a different logical "clump."
- Geometrically-Constrained Systems (GCS): This is a "relaxed" version of the theory. It explains how a model might not be able to perfectly recognize a language for infinite lengths, but can approximate it for very long sequences by using specific geometric shapes (like convex sets) in its state space.
Datasets and Benchmarks
The paper primarily uses formal language benchmarks to test the limits of model logic:
- Star-free regular languages: A class of logic problems that includes the FLIP-FLOP task (storing and resetting a bit).
- The Bhattamishra et al. (2023) benchmark: 11 tasks specifically designed to test the representational limits of sequence models.
- Chomsky Hierarchy tasks: Used to evaluate Mamba and xLSTM on tasks like counting and modular arithmetic (e.g., the Parity task).
- FLIP-FLOP instruction dataset: A predictive modeling task used for the paper's empirical visualizations.
Key Insights
- The "Contracting" Nature of Linear Models: The authors prove that any robust Linear Recurrent Dynamic (LRD)—the core of models like Mamba—is inherently "contracting." Over long sequences, the state eventually collapses into a single point, destroying long-term memory of discrete bits.
- xLSTM’s Non-linear Advantage: Because xLSTM uses non-linear gates (like exponential and sigmoid functions), it can create "strongly robust" states that do not collapse. This allows it to recognize all star-free languages perfectly, even in finite precision.
- Mamba’s "Piecewise" Success: If Mamba is theoretically limited, why does it work so well? The authors show that Mamba can use its state space to approximate logic using piecewise-linear boundaries. It’s not "recognizing" the language in a formal sense, but it’s approximating it well enough to generalize to longer sequences than it was trained on—until it eventually hits a limit and fails.
- The Parity Wall: The theory explains why Mamba fails at the Parity task (counting if a bit appears an odd or even number of times). Mamba’s geometry prevents it from "alternating" between states indefinitely; eventually, the linear recurrence forces the state to settle, losing the count.
Key Results
- Theorems 4 & 7: Linear models (SSMs/Mamba) cannot robustly recognize the FLIP-FLOP language. In experiments, a 1-layer Mamba model's state collapsed after approximately 1,000 inputs, leading to incorrect predictions.
- Theorem 5: xLSTM cascades can robustly recognize all star-free languages and can be implemented with standard floating-point operations.
- Theorem 8: While Mamba fails the strict "robust" test, it can recognize star-free languages as a Geometrically Constrained System, explaining its strong performance on many practical benchmarks.
- Empirical Validation: PCA visualizations of Mamba’s hidden states show the predicted "state-space collapse" in action, where two different initial states eventually merge into the same incorrect output.
Limitations and Future Work
- Complexity of Connections: While MAT handles the "memory" (state) well, it doesn't yet fully account for the complexity of the "connecting functions" (the MLP layers) between recurrent blocks.
- Training Dynamics: The current theory focuses on what a model can represent, not necessarily what a gradient descent algorithm will learn. The authors suggest that "robust" solutions are more likely to be learned, but more work is needed to prove this.
- Beyond Regular Languages: Future work aims to use the GCS framework to explore even more complex languages (like context-free languages) that require "counter-like" behavior, which remains a challenge for most modern architectures.
Summary updated