Where does a transformer keep its state?
Revised 26 October 2026; what changed is listed at the end.
When a language model has read a prefix, it is in some state: whatever it needs to remember to predict the rest. Formal language theory has a precise name for that state.
Myhill–Nerode: two prefixes are equivalent when every possible continuation gives them the same future. The equivalence classes are exactly the states of the smallest automaton for the language.
This definition does not mention any architecture. It only talks about behaviour, so it applies to a transformer, an RNN, or anything else that reads text. That makes it a candidate for describing what a network has learned in a way that survives a change of substrate.
My goal is to read these classes off a trained transformer from its weights alone, and to check the method on transformers compiled from known automata, where the right answer is known in advance. Before building that, I looked at where a trained transformer actually keeps this state.
The automaton
The whole note uses one small automaton. Picture a token on a ring of three groups, 0 → 1 → 2 → 0, with a coin next to it: the hidden bit. Every symbol moves both.
| Symbol | Group | Hidden bit |
|---|---|---|
0 | one step forward | flips |
1 | one step back | stays |
2 | forward if the bit is 0, back if it is 1 | resets to 0 |
The group decides what comes next: in group g the most likely next symbol is g (probability 0.55; the other two get 0.25 and 0.20). The bit has no say in that. It matters only when a 2 arrives, and it has a plain meaning: the bit is 1 when the number of 0s since the last 2 is odd.
That is what makes the automaton a test. After 0 it is in group 1 with bit 1; after 2, in group 1 with bit 0. Both prefixes predict the same next symbol. Add another 2 and they part: 02 steps back to group 0, 22 steps forward to group 2. They are two Myhill–Nerode classes that differ only later, so a model has to keep track of the bit before it ever needs it. Step through it here:
Try it
Below is the same automaton with a trained model next to it. The diagram shows its six states, labelled group·bit, and the arrows out of the current one.
A 2-layer transformer (my nanogpt) was trained on text sampled from this automaton, for 100,000 steps on fresh samples. It tracks the hidden bit on every prefix of up to 7 symbols. Type a prefix and compare the model with the automaton; Random draws a prefix from the automaton itself.
2. Same prefixes, one step later, coloured by the bit the prefix had. Now the colours split.Each dot is a prefix of up to 7 symbols in the same group as yours (about a third of all 3,279), projected to two dimensions with a PCA of the residual stream after the second layer, fitted within that group. Two dimensions hide a lot; finding 3 below measures the same effect in the full space. The model's loss is nats per symbol; the best possible is .
What I found
1. Classes that change the next symbol are visible at the current position
On random automata where every state predicts the next symbol differently, a linear probe recovers the class from the residual stream far better than position and last symbol alone can.
| Automaton | Probe on trained model | Position + last symbol | Probe on untrained model |
|---|---|---|---|
| 3 classes | 1.00 | 0.80 | 0.78 |
| 6 classes | 0.98 | 0.49 | 0.60 |
| 8 classes | 0.97 | 0.52 | 0.52 |
Residual stream after the last layer, one model per automaton. This is partly forced: the last layer has to tell these classes apart to predict the next symbol at all.
2. Differences that matter only later are mostly not stored there
When two classes predict the same next symbol and differ only further ahead, a probe after the last layer separates them with accuracy 0.87–0.92, against 0.84–0.85 from position and last symbol and 0.86–0.88 from an untrained model. The model does not need that difference yet, and mostly does not keep it in that vector. After the first layer the probe does a little better, 0.95, which fits the short window of recent symbols described in finding 3.
3. Over long gaps the hidden bit is mostly recomputed when it is needed
For the automaton in the demo, and for five random ones, I compared prefixes through their continuations: the residual stream after the second layer at the end of u followed by each short continuation w. The score is 0 when the hidden bit is invisible and 1 when it separates prefixes as much as a different group does. Five models per row; the range is over models.
| Automata | At the end of u | After w without a 2 (bit not needed yet) | After any w |
|---|---|---|---|
| Hand-chosen (demo) | 0.00–0.01 | 0.00–0.01 | 0.66–0.68 |
| Random, groups forced apart | 0.00–0.02 | 0.00–0.03 | 0.67–1.20 |
Every model reaches the optimal loss to within 0.006 nats and tracks the hidden bit on every prefix of up to 7 symbols. Scores above 1 mean that after a 2 the bit separates prefixes even more than a different group does.
This score compares whole vectors, so it could miss a bit kept in a small or nonlinear part of the vector. I therefore also trained probes, linear and a small MLP, to read the bit from the residual stream at the current position. In case the bit is spread across layers rather than held in one, as Shai et al. (2024) found in a similar case, I also probed the token embedding and both blocks concatenated. The last row is a baseline: it guesses the bit from the group, the last six symbols and the gap, so it catches everything a short window of recent symbols can explain.
Symbols since the last 2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11–13 | 14–23 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| MLP probe, last layer | 0.98 | 0.97 | 0.97 | 0.95 | 0.90 | 0.83 | 0.75 | 0.65 | 0.64 | 0.68 | 0.61 | 0.57 |
| MLP probe, all layers | 1.00 | 1.00 | 1.00 | 1.00 | 0.97 | 0.90 | 0.82 | 0.72 | 0.65 | 0.63 | 0.58 | 0.53 |
| Same probe, untrained model | 0.94 | 0.76 | 0.70 | 0.68 | 0.65 | 0.59 | 0.56 | 0.56 | 0.53 | 0.50 | 0.46 | 0.49 |
| Group + last six symbols | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | 0.99 | 0.69 | 0.65 | 0.64 | 0.52 | 0.52 | 0.43 |
Accuracy of predicting the bit on held-out sequences, averaged over the ten models; positions right after a 2 are left out, since the bit is always 0 there. Long gaps are rare (about 300 test positions at 14–23 across all models), so the last columns are noisy.
A probe trained on all positions sees few long gaps and may simply not learn them. Trained only on positions at least 11 symbols after the last 2, the MLP reads the bit with accuracy 0.62 on average, against 0.53–0.58 for the untrained twin and 0.50 for the majority class. The average hides a split: in two of the ten models the bit is readable at 0.81–0.84, in most of the others barely.
So the vector at the current position carries a window of recent symbols, five or six long when the layers are taken together, which is enough to recover the bit when a 2 was a few symbols back. Beyond that window most models keep at most a weak trace of the bit, and a few keep a partial running parity. Yet all of them apply the bit correctly after long gaps: right after a 2 the model picks the right next group 99.7% of the time when the previous 2 was up to six symbols back, and 96% of the time when it was ten or more. In most models, then, the bit is largely computed from the cache when the 2 arrives, and how much of it a model carries forward varies from seed to seed.
What follows
The state of a transformer is spread over its whole key-value cache. Each position keeps a short window of recent symbols, and older information that matters only later is mostly computed from the cache when it is needed. Nothing in the cache is ever overwritten: the prefix is all there. What compresses it is reading. Later positions see the past only through attention, so two prefixes are equivalent for the model when no continuation can read their caches differently.
That gives the goal a precise form. Treat the transformer as an automaton whose state is its cache, and compute its minimal automaton, the cache states modulo this indistinguishability, from the weights. The way there is to find what attention can read from the past: summaries of the prefix such as counts, parities, or the position of the last occurrence of a symbol, and show that the Myhill–Nerode classes are their level sets. Transformers compiled from known automata, where these summaries are put in by hand, are the test bed.
Related work
Belief states in the residual stream. Shai et al. (2024) show that transformers trained on data from hidden Markov models linearly represent the optimal belief state over the hidden states. The closest precedent to this note is their RRXOR process: belief states that predict the same next token were not separable in any single layer, only in the residual streams of all layers concatenated. They read this as support for the hypothesis that everything the future needs is present across the layers at each position. Finding 3 points the other way for most models here: at long gaps, concatenating the layers does not recover the bit, yet the model still applies it.
How transformers track state. Liu et al. (2023) prove that shallow transformers can simulate automata through parallel “shortcuts” rather than step-by-step recurrence, and Li, Guo and Andreas (2025) find associative-scan mechanisms of this kind in models trained to output the state of a permutation task; which mechanism a model learns varies across training runs, as it does here. In those tasks the state is the training target. Here it never is: the model only predicts the next symbol, and the interesting states are those that differ only later.
Extracting automata. Weiss, Goldberg and Yahav (2018) extract automata from RNNs with Angluin’s L*, answering equivalence queries through a partition of the hidden state. Adriaensen and Maene (2024) and Zhang, Wei and Sun (2024) carry the idea over to transformers, using activations as the state space. These methods learn the automaton from the model’s behaviour and activations on chosen inputs. The aim here is to compute it from the weights, so that the answer does not depend on which inputs were tried.
Programs and weights. RASP describes transformer computations as programs, and Tracr compiles such programs into weights, giving models with a known answer: the planned test bed. Huang et al. (2026) go the other way and decompile trained transformers into RASP programs, starting from a faithful re-parameterisation of the weights and pruning it with causal interventions. Their output is a program shaped like the network. The object sought here is the minimal automaton, which does not depend on the architecture; a decompiled program could be one route to it.
The cache as state. Oren et al. (2024) observe that a decoder-only transformer is an RNN whose state is its key-value cache, and use this to compress the cache. “What follows” uses the same view for interpretation: the minimal automaton is the set of caches modulo what later positions can tell apart.
Changes
26 October 2026. Finding 3 had compared the probe at long gaps with a baseline taken over all gaps, which overstated how little of the bit the current position keeps. With a baseline for each gap, probes trained on long gaps and the layers concatenated, it is weaker: most models keep a weak trace of the bit at long gaps, and two of ten keep much of it.
24 October 2026. The first version used undertrained models (3,000 steps on a fixed set of 5,000 sequences, tracking the bit about 87% of the time on 7-symbol prefixes), and two random automata had groups that predicted the next symbol almost alike. Every model was retrained for 100,000 steps on fresh samples, the random automata were redrawn with groups forced apart, and the demo got a hand-chosen automaton.