Discretizing Neural Activation Spaces into Finite State Automata

220 concepts119 papers2 proposals

Deep neural networks process information through high-dimensional, continuous vector spaces. While this continuity allows them to learn complex, non-linear mappings via gradient descent, it also makes their internal logic opaque and prone to error accumulation over long sequences. In contrast, classical computer science relies on discrete symbolic systems—like finite-state automata (FSAs) and Markov chains—which are perfectly interpretable, easily verified, and robust over infinite horizons.

A prominent research direction bridges this gap by mapping or constraining continuous neural hidden states into a finite set of discrete states. By treating the activation space not as an infinite continuum but as a collection of stable, functional regions, researchers can extract explicit symbolic rules from black-box models, verify their safety, and understand how they execute algorithms.

The Intuition: Why Continuous States Collapse

Why should a continuous neural network behave like a discrete state machine? When trained on structured sequence tasks (such as regular grammars, mathematical tracking, or algorithmic logic), networks naturally organize their internal activations into distinct, stable clusters. The continuous nature of the network does not inherently mean it utilizes infinite computational capacity; instead, it uses the continuous space to navigate between stable geometric configurations.

Early foundational work by Giles et al. and Watrous et al. demonstrated that recurrent neural networks (RNNs) trained on sequence tasks approximate finite-state behavior by organizing their hidden unit activations into well-separated regions. These regions serve as functional equivalents to the states of a finite-state machine.

More recently, van Rossem et al. showed that during training on algorithmic tasks like streaming parity, RNNs undergo a sudden phase transition: their continuous hidden trajectories merge into a clean, deterministic finite automaton. This internal discretization allows the network to transition from memorizing individual training examples to implementing a generalized, state-based logic that can extrapolate to sequences thousands of times longer than those seen during training.

This representational strategy is not unique to recurrent architectures. Du et al. discovered that Transformers utilizing chain-of-thought reasoning similarly organize their internal activations into non-overlapping clusters. Within these models, specific late-layer multilayer perceptron (MLP) neurons act as dedicated state trackers, mapping multiple distinct input paths that lead to the same logical conclusion onto a unified set of internal activations.

Post-Hoc State Abstraction

If a model naturally organizes its activations into discrete regions, how do we extract the underlying state machine? The standard post-hoc pipeline involves recording the network's hidden states over a dataset, reducing their dimensionality, and clustering them into discrete abstract states.

[Continuous Hidden States] ──> [Dimensionality Reduction (PCA)] ──> [Clustering (GMM/K-Means)] ──> [Discrete State Machine]

For example, the framework developed by Song et al. records hidden activations over a text dataset, reduces their dimensionality via Principal Component Analysis (PCA), and applies Gaussian Mixture Models (GMMs) to cluster the vectors. By treating the clusters as nodes and the token-driven movements between them as edges, the authors approximate the network's temporal logic as an explicit finite state machine.

In the context of large language models, this abstraction allows researchers to audit internal transitions as a symbolic system. Song et al. and Zhu et al. leverage this pipeline to translate high-dimensional transformer embeddings into abstract Markov chains or Hidden Markov Models. By analyzing the resulting state transition dynamics, they can systematically detect abnormal behaviors—such as hallucinations, adversarial attacks, and out-of-distribution inputs—based on whether the model's internal trajectory deviates into anomalous state sequences.

In-Training Discretization and Regularization

Instead of extracting an automaton after training, an alternative approach forces the neural network to operate discretely during training. This is achieved by introducing architectural bottlenecks or regularization terms that penalize continuous drift, forcing the network to offload its computation to stable state prototypes.

The authors of State-Regularized RNNs (Wang et al.) introduced a mechanism that restricts a network's hidden state to a probabilistic mixture of a fixed number of learnable centroid vectors. As Lawrence notes, this constraint regularizes the hidden state space, preventing the divergence of state values over long sequences and allowing researchers to directly extract human-readable deterministic finite automata without complex post-hoc clustering.

Similarly, König et al. passed the hidden state of an RNN through a softmax or hardmax layer, restricting the network's memory to a categorical distribution over a fixed number of states. To train this architecture effectively, the authors introduced a regularization term based on the cross-entropy loss between the predicted state distribution and its one-hot equivalent:

$$\mathcal{L}_{\text{reg}} = -\sum_{i} p_i \log(p_i)$$

This penalty pushes continuous neural activations toward discrete, binary logic during training, allowing standard gradient-based optimizers to find stable solutions that map directly to finite-state machines.

Verification and Safety Guarantees

Converting a continuous neural network into a discrete state machine is highly valuable for formal verification. Continuous neural networks are notoriously difficult to verify because their state space is uncountably infinite, making it impossible to exhaustively test every edge case.

To solve this, researchers partition continuous state spaces into finite, non-overlapping regions. For instance, Jin et al. partitioned continuous state spaces into axial bounding boxes where each region maps to a single discrete action, converting a complex neural network policy into a finite-state transition system.

As demonstrated by Jansen et al., quantizing the continuous hidden states of an RNN into a finite set of discrete memory nodes allows the conversion of non-linear internal representations into a format suitable for symbolic analysis. Once the policy is represented as a discrete state machine, developers can use standard model checking tools to mathematically prove whether a neural agent satisfies strict safety and performance requirements under Linear Temporal Logic (LTL) constraints.

Key Foundational Work

Higher Order Recurrent Networks and Grammatical Inference (1989) — contributed 2 concept elements to this direction.
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 2, frozen text):

@misc{lacuna_hidden_state_clustering_c77898c0_v2,
  title = {hidden state clustering},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hidden-state-clustering/rdr_c77898c0507641a18689b0806f7d03d5/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake