Length-independent state tracking interactive companion

Interactive illustration

Length-Independent State Tracking Under a Parallel Scan

To track a finite state at any sequence length, each update of a recurrent network has to remove its own numerical error and also carry out the next transition.

Code of the paper, available during the review period: github.com/dd8wgy467d-hash/reviewanonymous.

How to read this page

Keep the PDF open next to this page. The tag above each section, for example Paper §3, Thm 3.1, says which part of the paper it follows. Most figures run small toy models in your browser. Only the figures of §7 show results measured in the paper. The </> Code button flips a figure over to the code behind it, with your current settings highlighted.

PaperFigureWhat you do
§2, Defs 2.1 and 2.2N1, N2run an automaton; watch an affine RNN realize ℤ5, then lose it
§3, Thms 3.1 to 3.3, Fig. 1N3, N4switch restoration on and off; compare one rate with two
§4, App. E, Fig. 4N5, N6watch an exactly trained rotation drift; see which words a contracting model holds
§5, App. D, Fig. 3N7scan over tables, then over affine maps in fp16
§6, App. GN8, N9edit the logits of a Neural-FSM head; split S3 over two heads
§7.1, App. HN10, N11browse the failing lengths; read a TSO story
§7.2, App. I, Fig. 2N12, N13hold a spoken digit through noise; retrieve a needle with a pretrained Mamba-2

Paper §1, Introduction

1. Why ask for length independence?

State space models, gated linear RNNs and linear attention all scale for the same reason. Their recurrence is affine in the hidden state, so a parallel scan evaluates it in \(O(\log L)\) depth. When they are trained on state tracking, they do well up to the training length and fail soon after. Much of that failure comes from learning. The paper isolates the part that better training would not fix, finite precision. It asks what an RNN needs in order to track a state at every length, whether an affine recurrence can have it, and if not, whether some other scan-compatible recurrence can.

Section 7 checks the answers on synthetic automata, on spoken digits buried in hours of noise, and on a pretrained Mamba-2.

Paper §2, Formalization, State tracking and automata

2. Automata, RNNs, and finite precision

A task is a semiautomaton \((Q,\Sigma,\delta)\). Reading a word \(w\) moves the states by the composite map \(\delta_w\), and the set of all such maps is the transition monoid \(M_\delta\). Every task on \(n\) states lives inside \(T_n\), the monoid of all maps \(Q \to Q\), so an architecture that implements all of \(T_n\) covers every such task.

N1 A semiautomaton, and a word as the map \(\delta_w\) it induces on \(Q\).

Paper §2, eqs. (1) to (3), Definitions 2.1 and 2.2, App. D, Lemma D.1

Realization at finite precision

An RNN realizes the automaton when an encoding \(\iota\), an update \(\Phi_x\) and a readout \(\pi\) reproduce its runs (eq. 3). The paper models finite precision as an error of size at most \(\eta\) added at each step, and Lemma D.1 shows that every run of a real machine is such an η-trajectory. Length independence then asks for a correct readout on every η-trajectory (T1) and for a bounded reachable set \(U^\star\) (T2). Boundedness is what lets a fixed number of bits suffice at every length.

N2 runs the smallest affine realization of \(\mathbb Z_5\), \(A_x = \rho R(2\pi x/5)\), as a toy. The dashed disk contains the endpoint of every η-trajectory. Its radius obeys \(r_t = \rho\, r_{t-1} + \eta\), so at \(\rho = 1\) it grows by \(\eta\) at each step.

N2 An affine RNN realizing \(\mathbb Z_5\), under per-step perturbations of size \(\eta\).

Try Set \(\rho = 1\), tick worst case, then add samples: the disk crosses a cell boundary at \(L^\star\).

Paper §3, Theorems 3.1 and 3.2, eq. (4), Figure 1

3. Three conditions on one step, two rates in one map

Theorem 3.1 turns length independence into three conditions on a single step. (R1) asks for a code that can be decoded, (R2) for restoration, \(\Phi_x(U)\oplus\bar B_\eta \subseteq U\), and (R3) for the right transition even under perturbation. In geometric terms (eq. 4), each cell has to land inside the cell of its successor with \(\eta\) to spare. Von Neumann called the two jobs the executive organ and the restoring organ. In a recurrence, one map has to do both.

N3 Executing the transition and restoring the state (the paper's Figure 1, as a toy you can run).

Try Raise \(\lambda\) to 1: the reachable set widens every step until it straddles two cells.

Paper §3, Theorem 3.3; App. F, Lemma F.11

Two rates in one map

Iterated along a word, eq. (4) requires contraction inside each cell and separation between cells (Thm 3.3). The difficult words are those that keep two states apart, such as id in the flip-flop, and Lemma F.11 shows that every nondefinite automaton has one. N4 iterates a one-dimensional map from the two code points \(\pm1\), with \(\beta\) controlling how far the map is from affine. At \(\beta = 2\) the map contracts inside the cells and expands between them, and it holds both cells. At \(\beta = 0.3\) it is close to affine.

N4 Holding one bit: one rate everywhere (affine) against two rates in one map (multistable).

Try Move \(\beta\) from 0.3 to 2 and watch the second cell appear.

Paper §4.1, eq. (5), Theorem 4.1, App. C.2, App. E, Figure 4

4. An affine recurrence supplies a single rate

For an affine recurrence, \(\Phi_w(h) - \Phi_w(h') = A_w (h-h')\) (eq. 5). One matrix acts on the distance between two code points and on the perturbation alike, and Theorem 4.1 follows from this. When \(\rho(A_w)\ge 1\) for some word, perturbations build up and (R2) fails. When \(\rho(A_w) < 1\) for every word, the model forgets old inputs together with the perturbation and can realize at most a definite automaton. Table 3 (App. C.2) places most scan-compatible architectures on one branch or the other. The theorem is a worst-case statement. No affine recurrence is guaranteed correct at every length, although a given run can be.

Perfect training does not remove the problem (App. E). N5 starts from the exact \(\rho = 1\) realization of \(\mathbb Z_7\), a rotation by \(2\pi/7\). It rounds the entries once to a number format, then runs in fp64 so that nothing else gets rounded. The stored rotation turns by a slightly wrong angle and its radius is slightly off 1. The phase error grows at every step until the readout picks the wrong state.

N5 The exact \(\mathbb Z_7\) rotation, rounded once to each format, then run in fp64 (the paper's Figure 4).

Try Play in bf16, then in fp32. The readout fails in both; fp32 only fails later.

Paper §4.1, Def. F.10, Prop. F.13, §7.1, Table 1

Forgetting is harmless only for definite targets

A definite automaton only depends on its last \(k\) inputs, and for these targets a contracting affine map is enough (Prop. F.13). The flip-flop sits on the boundary. DFF5 never draws more than four identities in a row, while FF allows runs of any length. N6 runs a toy contracting tracker on each.

N6 A contracting tracker holds definite words and loses the others.

Paper §4.2, Lemma F.17, Prop. F.22, Theorem F.25

Two rates require multistability

On a nondefinite target, eq. (4) asks one update map to hold a separate cell for each automaton state. An affine map that restores has only one fixed point, so it holds one cell whatever its width (Prop. F.22). Stacking affine layers does not help, whatever nonlinear maps sit between them (Thm F.25). The nonlinearity has to act on \(h_{t-1}\) itself (Lemma F.17). PD-SSM's hardmax picks a transition matrix from the input and never touches the hidden state, so each PD-SSM step is still affine.

Paper §5, Definition 5.1, Proposition 5.2

5. Scan compatibility is a budget on the representation

For a parallel scan, each composite \(\Phi_w\) has to fit in \(b\) bits, and two composites have to merge in \(c\) operations (Def. 5.1). Under that budget only finitely many hidden states can be reached, and on them the recurrence behaves like a lookup table (Prop. 5.2). A recurrence with exact restoration sends every basin to a single attractor. Each symbol is then a table over \(K\) indices, stored in \(K\lceil\log_2 K\rceil\) bits and merged with one lookup per index, and the merge adds no error.

N7 (a) A parallel scan over transition tables. Every merge is a gather, and the result is exact.

Paper §5, App. D, Figure 3

Affine composites get rounded. Floating-point arithmetic is not associative, so the scan and the sequential loop give different trajectories for the same affine model, which makes the scan one more source of \(\eta\). Figure 3 of the paper measures the gap on the five affine baselines. N7 (b) shows it on two toy affine models.

N7 (b) The same toy affine model, evaluated sequentially and by a parallel scan, drifts apart.

Paper §6, eq. (6), Props. G.1 to G.3

6. The neural finite-state machine

A Neural-FSM head updates its state with \(\Phi_x(h) = \mathrm{rd}(\theta_x\, \mathrm{rd}(h))\) (eq. 6). Here \(\mathrm{rd}\) returns the one-hot vector of the largest coordinate, and \(\theta_x\) is a logit matrix computed from the input. Multiplying by \(\theta_x\) carries out the transition, sending index \(k\) to the row where column \(k\) has its largest entry. The outer \(\mathrm{rd}\) does the restoring and puts the result back on a code point. On a trajectory \(h\) is already a basis vector, so the inner \(\mathrm{rd}\) changes nothing.

If the head's tables equal the target's, the head realizes the target (Prop. G.2). By Prop. G.3, a logit perturbation smaller than half the smallest column margin \(\gamma\) leaves all the tables as they are, at any length.

N8 One Neural-FSM head: logits, then table, then run.

Try Click the dashed cell of each wrong column until every column shows ✓.

Paper §6, Prop. G.4, Example G.7, App. H.7.2, Table 7

Heads as memory channels

A layer is a block of heads that read the same input and update independently (Prop. G.4). Splitting the state over heads also saves logits. Tracking \(k\) quantities of \(v\) values each costs \(k v^2\) logits per step with one head per quantity, and \(v^{2k}\) with a single head. The trained \(S_3\) model of seed 42 uses two heads. The 3-index head follows where point 1 goes, and the 2-index head follows the sign of the permutation.

N9 \(S_3\) carried by two heads, with the tables extracted from the trained model (seed 42).

Paper §6, App. G.6, App. H.8, Table 8

What a layer costs

A table depends on its symbol only, so a head computes all the tables of a sequence at once and combines them with a scan whose merges are gathers. Gradients pass through the arg max with a straight-through Gumbel-softmax estimator. Table 8 of the paper times one layer of each model in a training step, forward and backward, with the parallel scan, \(d = 16\), a batch of 16 and one A100.

ModelBranchParametersLmax on S4ms, L = 212ms, L = 217GB, L = 212GB, L = 217
Neural-FSMrestoring0.17M≥ 1M†1.843.80.516.0
Mamba−ρ < 10.76M1053.3109.31.032.0
PD-SSMρ < 15.56M1315.2117.81.548.0
minGRU−ρ < 10.70M930.815.10.516.0
AUSSMρ = 14.94M893.8115.61.048.0
DeltaProductρ = 11.10M2579.0287.63.050.6

Parameters: whole model of Table 1 on S4 (the Neural-FSM has one layer of heads (4, 3, 2), the baselines four layers of width 256). Peak memory is an approximate measurement (App. H.8).

Paper §7.1, Table 1, App. H.4, Table 5

7. Experiments

Synthetic finite-state tracking

The baselines are five affine recurrences, chosen to cover both branches of Theorem 4.1. Mamba−, minGRU− and PD-SSM contract (\(\rho < 1\)), and AUSSM and DeltaProduct have \(\rho = 1\). Every model uses the same backbone. Each baseline has four layers of width 256, while the Neural-FSM uses a single layer on the algebraic tasks and two on TSO. Training uses sequences of one fixed length, and testing uses longer ones.

A single Neural-FSM layer is perfect up to the longest tested length on every algebraic task and all five seeds, and two layers are perfect on TSO. Most baselines break within a few hundred steps or never learn the task. As Theorem 4.1 predicts, the contracting baselines hold DFF5 and fail on FF. Baselines that do learn a task reach very different lengths from one seed to the next.

N10 Failing length on algebraic and textual state-tracking tasks (Table 1, with the seeds of Table 5).

Paper §7.1, App. H.7

Reading the tables off a trained model

Each step of a Neural-FSM commits to one table entry, so the tables of a trained model can be read from its logits and compared with the target. They match on every algebraic task and every seed. Props. G.2 and G.4 then give correctness at every length, as long as the logit margin is larger than the error in computing the logits. On M11, for example, the four 11-index heads reach 7920 of the 14641 joint indices, one per group element.

Paper §7.1, App. H.1, App. H.7.3, Figure 6

Tracking Shuffled Objects

TSON asks the same algebraic question in words. People swap items, and at the end a question asks who has one of them. In the trained two-layer Neural-FSM on TSO4, each head of the second layer follows the holder of one item. No first-layer head matches a single register when looked at alone, but together they pass the parse up to the second layer. The paper inspects this stack by hand and does not certify it by extraction.

N11 A TSON stream and the automaton state it drives.

Try Drag the tokens-read slider through the story and watch the state (p, g) follow.

Paper §7.2, Figure 2A, App. I.1, Figure 8

Real data: a spoken digit in a stream of noise

Real data do not come with a labelled state, so the model has to find one itself. Theorem 4.1 gives two ways for an affine recurrence to lose it. With strong contraction, every input is forgotten after a fixed number of steps, as in a \(k\)-definite system. With weak or no contraction, perturbations build up until the state collapses, wherever the important input was.

The keyword-spotting task streams background noise that may contain one spoken digit from Speech Commands. At the end of the stream the model names the digit or says "none", and nothing else is supervised. Training streams last a few seconds, and test streams last up to 8192 s, a little over two hours. The Neural-FSM (four layers of 64 heads with 4 indices each) keeps its accuracy at every tested length, whether the noise comes before or after the digit. On short streams the affine models do better, around 96% against 93%. N12 puts each model next to the pattern the theory predicts for it.

N12 Top: the three patterns Theorem 4.1 predicts. Below: digit accuracy against the noise before the digit (no noise after) and after it (no noise before). Line: median over three seeds; band: range.

Try Play the stream, then pick a pattern to compare theory and data.

Paper §7.2, Figure 2B, App. I.2, Figure 9

A pretrained Mamba-2 on a needle in a haystack

The RULER task niah_single_1 hides a key and its value in distractor text, with \(L_\text{pre}\) tokens before this needle and \(L_\text{post}\) tokens between the needle and the question. In Mamba-2 780M as released, the decay is below 1 but too close to 1 to remove the perturbations, which pile up as on the \(\rho = 1\) branch. Accuracy depends on \(L_\text{pre} + L_\text{post}\) and falls to zero beyond a fixed total length. This happens even when the needle comes right before the question.

The paper then forces every head to decay fast enough that its memory fades within about \(\tau\) tokens, with no retraining. This moves the model to the contracting branch, where it behaves as a \(k\)-definite system. It finds the needle whenever the needle is within about \(\tau\) tokens of the question, for every \(L_\text{pre}\) tested up to 128k. WikiText-2 perplexity goes from 14.68 to 14.74, 14.88 and 15.52 for \(\tau\) = 2048, 1024 and 512. The 130M and 370M models behave the same way, and so does the 780M model with the instruction moved or removed.

N13 Mamba-2 780M on RULER niah_single_1: accuracy over \(L_\text{pre}\) and \(L_\text{post}\), as released and with the decay bounded by \(\tau\). ppl is WikiText-2 perplexity. The two left panels are the patterns Theorem 4.1 predicts. The image is the paper's Figure 2B.
Heat maps of retrieval accuracy over the tokens before and after the needle: as released, accuracy vanishes past a fixed total length; with the decay bounded by tau, the needle is retrieved whenever it lies within about tau tokens of the question.
PanelPatternWhat to look for
collapsing (theory)ρ = 1 branchAccuracy is lost once \(L_\text{pre} + L_\text{post}\) passes a constant \(C\). The edge of the coloured region is a curve of constant total length.
\(k\)-definite (theory)ρ < 1 branchOnly \(L_\text{post}\) matters. The needle is found below a horizon \(k\), and the edge is a horizontal line.
Mamba2 780M, as releasedcollapsingThe coloured region ends along the curved edge. A long \(L_\text{pre}\) alone makes retrieval fail, even with the needle next to the question.
\(\tau\) = 2048, 1024, 512\(k\)-definite, \(k \approx \tau\)The edge is a horizontal line near \(L_\text{post} = \tau\), the same for every \(L_\text{pre}\) up to 128k. Smaller \(\tau\) moves it down and raises the perplexity.

Paper §8, App. B

8. Discussion

A finite representation budget leaves the recurrence only finitely many reachable hidden states. If those states are far enough apart, a single map can remove the error of each step and also perform the next transition. An affine recurrence has only one rate. At finite precision it therefore either lets perturbations grow or realizes at most a definite automaton, and more width or depth does not change this.

A model built on a contracting recurrence has a context window that nobody declared. Old inputs reach the output only through a term that shrinks geometrically. Past a length fixed by the learned gates and the perturbation floor they are lost in the noise, and nothing signals when that length is exceeded. Bounding the decay of the pretrained Mamba-2 turns this window into a declared one.

The paper recommends restorative recurrences, which return the state to a finite set of attractors at every step, and the Neural-FSM is one of them. Tasks whose state set must grow with the input, such as counting without a modulus or matching nested brackets, fall outside this setting and are left open.