Warm Starting State-Space Models with Automata Learning

William Fishell; Sam Nicholas Kouteili; Mark Santolucito

cs.LGMar 5, 2026

Warm Starting State-Space Models with Automata Learning

Authors: William Fishell, Sam Nicholas Kouteili, Mark Santolucito

Organizations: Columbia University · Yale University · Barnard College, Columbia University

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.

Figures & tables

Table 1

Figure 1: Warm-starting SSM using symbolic structure VS. learning using traditional random initialization on an dynamic round robin arbitration policy with 4 channels.

Panel of Figure 2 — Figure 2: Highlevel training pipeline visualization for learning regular languages from SYNTCOMP

Panel of Figure 3 — Figure 3: Methodology for generating assumption following traces by randomly picking transitions from states, generating assumption abiding traces

Panel of Figure 5 — Figure 5: SSM architecture used to learn SYNTCOMP regular languages

Figure 6: Accuracy and sample complexity (Log Scale) for learning a random subset of 20 SYNTCOMP examples

Learning Method	Perfect Emulation
Gradient-based SSMs	33.3%
L ∗	77.3%
RPNI	56.0%

Table 2: Percentage of SYNTCOMP benchmarks solved with 100% accuracy by each learning method.

Figure 7: Training and Testing Accuracy on Predicting Next Step and Trace Acceptance for collector/parametric/collector_v2, N=3

Figure 8: PCA projection of SSM hidden states after processing 1,000 random length-5 traces, colored by ground-truth automaton state. Counts indicate traces terminating in each state.

A\leftarrow I+\mathcal{N}(0,\varepsilon),\text{ where

A_{ij}=0

}

Algorithm 1 Symbolic Initialization of an SSM from a Moore Machine

Figure 9: Learning and performance of SSMs learning dynamic arbitration policies over various arbiter settings. Warm-start VS. random initialization. N denotes parameterization

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmark	SSM Acc (%)	L* Acc (%)	RPNI Acc (%)	SSM Samples	L* Samples	RPNI Samples
$\mathtt{01}$	26.9	100.0	100.0	8,100,000	6,346	5,000
$\mathtt{02}$	7.6	100.0	100.0	8,100,000	6,440	5,000
$\mathtt{03}$	2.3	99.0	0.0	8,100,000	79,764	5,000
$\mathtt{EscalatorSmart}$	0.0	100.0	100.0	8,100,000	6,959	5,000
$\mathtt{Gamemodule}$	0.2	100.0	100.0	8,100,000	4,721	5,000
$\mathtt{KitchenTimerV1}$	100.0	100.0	100.0	4,500,000	1,878	5,000

Appendix

Table 3: Comparison of learning methods on SYNTCOMP benchmarks.

Figure 14: Adaptive arbiter results 1. Shown in main paper

Automata Learning

See all 15 papers

A Comparative Analysis of Attention versus State-Space Models for In-Context Learning
Sep 26, 2026Enes Arda, Semih Cayci, Atilla EryilmazState Space Models In-Context Learning
The Ohio State University · RWTH Aachen University
Error-awareness Accelerates Active Automata Learning
Feb 25, 2026Loes Kruger, Sebastian Junges, Jurriaan RotAutomata Learning Active Learning
Institute for Computing and Information Sciences, Radboud University, Nijmegen, the Netherlands
On the Importance of Gating: Memorization vs. In-Context Learning in State Space Models
Sep 15, 2026William L. Tong, Aryo Lotfi, Emmanuel Abbe +6Memorization in Language Models Long-Context Modeling
Harvard University · Apple

Sep 26, 2026J/K move · Enter open · S save

A Comparative Analysis of Attention versus State-Space Models for In-Context Learning

Enes Arda, Semih Cayci, Atilla Eryilmaz

The Ohio State University · RWTH Aachen University

State Space Models In-Context Learning Selective SSMs Softmax Attention

Open paper AskPDF arXiv

Transformers and state-space models (SSMs) are two prominent sequential learning architectures, yet their comparison remains largely empirical and existing theoretical analyses are typically task-specific or architecturally restricted. In this paper, we develop belief geometry, a unified analytical framework for comparing the representational capabilities of broad classes of attention and SSMs. Starting from a generalized formulation of in-context linear regression and using cumulative Bayes regret as our measure, we abstract three capabilities required by many sequential learning problems in our belief geometry: evidence assembly, belief maintenance, and addressing. We then study three cases of our formulation that isolate these capabilities and yield sharp architectural lessons: For belief maintenance, SSMs attain the optimal regret over stationary aggregation kernels; for positional assembly, SSMs have a memory advantage; and for content addressing, softmax attention has an exponential width advantage over sigmoid-selective SSMs. Experiments with LLaMA-type Transformers and Mamba-2 show that these architectural insights extend beyond our analytically tractable classes and linear-regression testbed.

Abstract

Automata Learning

Explore similar work

A Comparative Analysis of Attention versus State-Space Models for In-Context Learning

Error-awareness Accelerates Active Automata Learning

On the Importance of Gating: Memorization vs. In-Context Learning in State Space Models