Mapping Continuous Neural Representations to Discrete State Machines

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2117 papers181 conceptsfrozen 2026-10-04

Recurrent Neural Networks (RNNs) and Transformers are often described as "black boxes" because their internal logic is buried within high-dimensional, continuous vector spaces. However, when these models learn to process structured sequences—like programming languages, regular grammars, or logical protocols—they don't just perform "fuzzy" pattern matching. Instead, they often organize their internal activations into stable, discrete regions that function as the states of a symbolic machine.

By extracting these hidden structures, researchers can translate opaque neural weights into human-readable Finite State Automata (FSA). This process bridges the gap between connectionist learning and symbolic logic, allowing us to verify, debug, and compress complex models.

The Intuition of State Space Partitioning

The core idea is that a trained recurrent model must maintain a "memory" of its history to predict the next token. In a continuous network, this memory is a hidden state vector. While this vector can technically exist anywhere in a high-dimensional space, researchers like C. Lee Giles and Guo-Zheng Sun discovered as early as 1989 that these vectors naturally form clusters.

In Higher Order Recurrent Networks and Grammatical Inference, they showed that if a network learns a language like balanced parentheses, its hidden states don't drift aimlessly. Instead, they gravitate toward specific "attractors" in the state space. Each attractor corresponds to a logical state—for example, "one open parenthesis pending" or "balanced." By partitioning the continuous state space into discrete bins, we can treat the network as a Deterministic Finite Automaton (DFA).

From Continuous Trajectories to Symbolic Transitions

To extract a symbolic model, we typically follow a three-step pipeline:

  1. Observation: Run the model on a large dataset and record the "trajectories" of its hidden states.
  2. Discretization: Use dimensionality reduction (like PCA) and clustering algorithms (like k-means or Gaussian Mixture Models) to group similar hidden states into a finite set of abstract states. Da Song and Lei Ma demonstrate this in DeepSeer, where they map RNN activations to human-interpretable semantic categories.
  3. Transition Mapping: Observe how an input token $x$ moves the model from cluster $A$ to cluster $B$. This defines the edges of our extracted state machine.

As Raymond L. Watrous and Gary M. Kuhn noted in Induction of Finite-State Automata Using Second-Order Recurrent Networks, this extracted machine often generalizes better than the original neural network. Because the symbolic model eliminates the numerical drift inherent in floating-point math, it can process sequences of arbitrary length without the "forgetting" that plagues standard RNNs.

Forcing Logic via State Regularization

While some networks naturally discretize their states, others remain stubbornly "mushy," making extraction difficult. To solve this, Cheng Wang introduced State-Regularized Recurrent Neural Networks.

Instead of allowing the hidden state to be any arbitrary vector, an SR-RNN forces the state to be a stochastic mixture of a few learnable "centroids." This architectural constraint acts as a bottleneck, forcing the network to offload its complex logic into transitions between these stable points. This makes the resulting model's internal logic directly extractable as a flowchart, providing a "white-box" explanation of its predictions.

Scaling to Transformers and LLMs

The same principles are now being applied to modern architectures. In Extracting Finite State Machines from Transformers, Jaron Maene and Rik Adriaensen use $L^*$ learning algorithms to extract Moore machines from Transformers, revealing that these models often fail to learn "garbage states" (error-handling logic) when trained only on positive data.

Similarly, frameworks like LUNA and PoLLMgraph by Derui Zhu and colleagues map the internal transitions of Large Language Models (LLMs) to Markov Chains. By analyzing these state transition dynamics, they can detect hallucinations and adversarial attacks: if a model's internal state moves into an "abnormal" region of the abstract state space, it is a strong signal that the output is unreliable.

Why Extraction Matters: Verification and Safety

The ultimate goal of this research direction is not just interpretability, but formal verification. In safety-critical domains, we cannot rely on a "black box" policy.

By converting neural policies into finite-state controllers, researchers like Nils Jansen have shown in Verifiable RNN-Based Policies for POMDPs that we can use standard model-checking tools to prove a model will never enter a "dangerous" state. This transformation allows us to enjoy the learning power of deep networks while maintaining the rigorous guarantees of symbolic logic.

Papers in this version

Showing 60 of 117 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 132 papers
  2. Version 1 · 2026-10-04 · 117 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_hidden_state_clustering_c77898c0,
  title = {hidden state clustering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hidden-state-clustering/rdr_c77898c0507641a18689b0806f7d03d5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_mapping_continuous_neural_representation_c77898c0_v1,
  title = {Mapping Continuous Neural Representations to Discrete State Machines},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/mapping-continuous-neural-representations-to-discrete-state-machines/rdr_c77898c0507641a18689b0806f7d03d5/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}