Warm Starting State-Space Models with Automata Learning
William Fishell, Sam Nicholas Kouteili, Mark Santolucito † · 2026
Read Warm Starting State-Space Models with Automata Learning by William Fishell, Sam Nicholas Kouteili, Mark Santolucito † (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-05694.txt.
Introduction
Fishell and team prove exact building of Moore machines as state-space models. These Moore-SSMs keep the original machine's symbol structure and input-output action in Euclidean space. Weighing SSM training with passive and active automata learning, SSMs need far more data than symbol methods. SSMs also fail to learn state structure. Symbol structure provides a strong built-in bias, and starting SSMs with symbol-learned guesses learns faster and better. Closing in runs 2-5 times faster than random start, with better scores.
Catalog record
| CREATOR | William Fishell, Sam Nicholas Kouteili, Mark Santolucito † |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56689 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.05694
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Warm Starting State-Space Models with Automata Learning William Fishell, Sam Nicholas Kouteili, Mark Santolucito † Abstract We prove that Moore machines can be exactly realized as state-space models (SSMs), establishing a formal correspondence between symbolic automata and these continuous machine learning architectures. These Moore-SSMs preserve both the complete symbolic structure and input-output behavior of the original Moore machine, but operate in Euclidean space. With this correspondence, we compare the training of SSMs with both passive and active automata learning. In recovering automata from the SYNTCOMP benchmark, we show that SSMs require orders of magnitude more data than symbolic methods and fail to learn state structure. This suggests that symbolic structure provides a strong inductive bias for learning these systems. We leverage this insight to combine the strengths of both automata learning and SSMs in order to learn complex systems efficiently. We learn an adaptive arbitration policy on a suite of arbiters from SYNTCOMP and show that initializing SSMs with symbolically-learned approximations learn both faster and better. We see 2-5 times faster convergence compared to randomly initialized models and better overall model accuracies on test data. Our work lifts automata learning out of purely discrete spaces, enabling principled exploitation of symbolic structure in continuous domains for efficiently learning in complex settings. 1 Introduction Symbolic learning methods such as active and passive automata learning [ 6 , 33 ] are highly effective for systems that admit finitely representable behavioral models. These methods have been widely applied to infer models of network and communication protocols [ 3 ] , where they infer behavioral models by treating the target system as a black box. Automata learning recovers symbolic structure: explicit, discrete representations of state, transitions, and outputs that fully characterize system behavior over a finite set of configurations. However, these methods face key limitations: passive learning struggles to scale to complex problems, while active learning is bottlenecked by the cost of membership and equivalence queries [ 4 ] . The discrete nature of automata compounds these challenges, as there is no notion of proximity between behavioral models; solving a simpler problem provides no initialization for learning a related but more complex target. Furthermore, systems that track things about cumulative quantities, such as version control histories or API request counts, are fundamentally beyond the reach of classical automata learning. These methods recover finite-state representations, yet systems where behavior depends on the entire unbounded history require infinite memory. We address these problems by formalizing the relationship between Moore machines and state-space models (SSMs) [ 17 ] . SSMs are continuous-state recurrent models that process sequences through learned linear dynamics. SSMs such as Mamba [ 16 ] have received growing interest as they present a computationally efficient alternative to Transformer architectures that can compute linear attention. Beyond efficiency, we find that SSMs can realize Moore machines exactly. Representing Moore machines as SSMs yields three benefits: we inherit symbolic structure as an inductive bias, gain access to a continuous space where proximity can be exploited, enabling gradient-based refinement toward more complex settings, and can leverage recurrence to more easily model infinite-state systems. This correspondence provides an end-to-end pipeline where automata learning extracts structure that initializes continuous models, extending the reach of symbolic methods and enabling more efficient learning in deep learning settings. We evaluate our approach of symbolic warm-starting on a suite of arbiters from SYNTCOMP. These systems have an underlying control policy described by a finite-state arbiter. We then augment this base policy such that the arbiter must track each channel’s deviation from the average number of grants. Computing this deviation requires tracking grants across the entire history, demanding theoretically infinite memory. Such systems cannot be captured exactly by finite-state machines, making them natural candidates for neural approaches initialized with symbolic structure. To motivate this hybrid approach, we first establish the value of symbolic structure in purely finite-state settings. We evaluate sample efficiency of symbolic and neural methods on a suite of regular languages from SYNTCOMP. Active learning (L*) and passive learning (RPNI) are compared against randomly initialized SSMs trained via gradient descent. This baseline experiment measures how many samples each method requires to recover a target automaton’s behavior. Automata learning achieves significantly greater sample efficiency than neural approaches trained from scratch. This motivates our use of symbolic structure as initialization for learning systems that extend beyond finite-state representations 1 1 1 All code available at https://github.com/wfishell/Automata_SSM_Learning/tree/main . In all, the key contributions of this work are as follows: 1. To the best of our knowledge, we are the first to initialize SSMs from automata recovered via classical learning algorithms, enabling more sample-efficient learning of complex settings. 2. We formalize a proof that Moore machines admit exact realizations as SSMs, preserving both structure and behavior. 3. We present an empirical study on SYNTCOMP benchmarks showing that symbolic methods achieve orders of magnitude greater sample efficiency than gradient-trained SSMs. 2 Motivating Example Cloud resource allocation is an important task in managing customer access to cloud resources by providers like Amazon Web Services (AWS) [ 5 ] . Modeling and verifying allocation protocols has been a focus of formal methods research [ 8 , 12 , 15 ] . Additionally, machine learning techniques have been increasingly used for modeling more complex resource allocation schemes [ 35 , 29 ] . Furthermore, warm-starting—initializing a model with parameters learned from a simpler setting before training on more complex instances—has also proven effective for cloud resource allocation. Prior work uses warm-starting in neural models for cloud resource allocation and relies on simpler neural architectures and unsupervised methods [ 25 ] . Our work bridges formal and neural approaches by using symbolic structure to warm-start neural models for efficient learning of adaptive arbitration policies in cloud resource allocation. Example 1 (GPU Allocation System) Company A is a cloud GPU provider that has four customers and an 8-GPU cluster. Company A has a policy for granting access to their network based on a round robin arbiter with the added safety constraint that no user can request more than 25% of the network’s capacity. Once a GPU is allocated, it is live for the entire hour. Afterward, the user is kicked off the network. Day Hour Req. Action C1/C2/C3/C4 Tot. Mon 00:00 C1 Grant 2/0/0/0 2 Mon 00:00 C1 Grant 2/0/0/0 2 Mon 00:00 C1 Rej. 2/0/0/0 2 Mon 01:00 C1 Grant 2/0/0/0 2 Mon 01:00 C1 Grant 2/0/0/0 2 Mon 01:00 C1 Rej. 2/0/0/0 2 Mon 02:00 C1 Grant 1/0/0/0 1 Mon 03:00 C1 Grant 2/0/0/0 2 Mon 03:00 C1 Grant 2/0/0/0 2 Mon 04:00 C1 Grant 2/0/0/0 2 Mon 04:00 C1 Grant 2/0/0/0 2 Mon 04:00 C1 Rej. 2/0/0/0 2 Mon 05:00 C1 Grant 2/0/0/0 2 Mon 05:00 C1 Grant 2/0/0/0 2 Mon 08:00 C2 Grant 0/2/0/1 3 Mon 08:00 C2 Grant 0/2/0/1 3 Mon 08:00 C4 Grant 0/2/0/1 3 Mon 09:00 C2 Grant 0/1/0/2 3 Mon 09:00 C4 Grant 0/1/0/2 3 Mon 09:00 C4 Grant 0/1/0/2 3 Mon 10:00 C3 Grant 0/0/2/0 2 Mon 10:00 C3 Grant 0/0/2/0 2 Mon 11:00 C4 Grant 0/0/0/1 1 (a) Round robin arbiter, hard 25% reject Day Hour Req. Action C1/C2/C3/C4 Tot. Mon 00:00 C1 Grant 2/0/0/0 2 Mon 00:00 C1 Grant 2/0/0/0 2 Mon 00:00