Length-Independent State Tracking Under a Parallel Scan

Julien Brandoit; Arthur Fyon; Thomas Braipson; Tom Clara; Florent De Geeter; Pierre Sacré; Damien Ernst; Guillaume Drion

cs.LGSep 26, 2026

Length-Independent State Tracking Under a Parallel Scan

Authors: Julien Brandoit, Arthur Fyon, Thomas Braipson, Tom Clara, Florent De Geeter, Pierre Sacré, Damien Ernst, Guillaume Drion

Organizations: Montefiore Institute, University of Liège Liège, Belgium

Abstract

Learning robust and scalable finite-state tracking is fundamental to sequence processing. While linear recurrent neural networks (RNNs), linear attention, and state space models enable scalable parallel training through affine recurrences, their theoretical expressivity guarantees assume idealized arithmetic and do not extend to finite precision, where the parallel scan that makes them fast is itself a source of perturbation. We formalize finite-state tracking at finite precision and characterize length independence: tracking that stays correct at every sequence length, at a precision cost that does not grow with the length. We show that length-independent state tracking requires two competing dynamics within a single map: contraction to suppress numerical perturbations and separation to keep distinct states apart. We prove that affine recurrences, which offer a single rate at each step to serve both roles, realize at most definite automata at finite precision. Instead of treating scan compatibility as a restriction on the update map, we reinterpret it as a computational budget and introduce the Neural Finite-State Machine (NFSM): a nonaffine, scan-compatible RNN built for length-independent finite-state tracking. On synthetic benchmarks spanning abelian and nonabelian groups, noninvertible monoids, and textual state-tracking tasks, affine baselines fail on every nondefinite task, most of them within a few hundred steps. A single NFSM layer instead learns the exact transition tables of every algebraic task, which certifies correctness beyond the tested lengths, and a stack of NFSMs keeps perfect accuracy on the textual tasks at every tested length.

Figures & tables

Panel of Figure 1 — Figure 1: Length independence requires executing the transition and restoring the state. The same automaton (left), realized twice and unrolled over time; the top strip is its run on $w$ . The vertical axis sketches $\mathcal{H}$ , with the bounded region $U$ split into the cells $U_{q}=\{u\in U:\pi(u)=q\}$ , drawn as bands, and the code points $\iota(q)$ as red dots. Top : \scriptsize1⃝ the update moves the hidden state into the next cell, and computing it spreads the state over $\bar{B}_{\eta}$ ; \scriptsize2⃝ restoration pulls that ball back onto the code point, so $\pi(h_{t})=q_{t}$ at every length. Bottom : nothing pulls the hidden state back, so the ball grows by $\eta$ per step and at $t=5$ straddles $U_{q_{3}}$ , $U_{q_{4}}$ and $U_{q_{5}}$ ; the single symbol $a$ then drives three runs at once (dashed) and $\pi(h_{t})$ is not unique anymore.

Panel of Table 1 — Table 1: Failing length on algebraic and textual state-tracking tasks. Each cell reports the median failing length $L_{\max}$ over the seeds that learned the task, and below it how many of the five seeds did (Appendix H.4 ). $\geq L$ : no failure up to $L$ , the longest sequence that fits on one GPU. † : the extracted tables match the target exactly, which certifies correctness at every length (Appendix H.6.2 ). $\times$ : no seed learned the task. Brackets below the task names give the number of reachable states.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Target		Model
$\Sigma,\Sigma^{*}$	alphabet; free monoid of words, with $\Sigma^{+}=\Sigma^{*}\setminus\{\varepsilon\}$ .	$\mathcal{H}=\mathbb{R}^{d}$	hidden state space
$Q$ , $n$	automaton state set; $n\coloneq\|Q\|\geq 2$	$\Phi_{x}$ , $\Phi_{w}$	per-symbol map; composite $\Phi_{wx}\coloneq\Phi_{x}\circ\Phi_{w}$
$\delta_{x},\delta_{w}$	symbol action $\delta_{x}\coloneq\delta(\cdot,x):Q\to Q$ ; extension to words, $\delta_{w}\coloneq\delta_{x_{\|w\|}}\circ\cdots\circ\delta_{x_{1}}$	$A_{x},b_{x}$	affine data, $\Phi_{x}(h)=A_{x}h+b_{x}$
$M_{\delta}$	transition monoid, $M_{\delta}=\{\delta_{w}\mid w\in\Sigma^{*}\}\leq Q^{Q}$ , under composition	$A_{w}$	$A_{x_{\|w\|}}\cdots A_{x_{1}}$ for $w=x_{1}\cdots x_{\|w\|}$
$Q^{Q}$	all maps $Q\to Q$ under composition; $Q^{Q}\cong T_{n}$ , $M_{\delta}\leq Q^{Q}$	$\rho$ , $\kappa$	spectral radius; $\kappa\coloneq\max_{x}\\|A_{x}\\|_{\mathrm{op}}$ , with $\\|A\\|_{\mathrm{op}}\coloneq\sup_{v\neq 0}\\|Av\\|/\\|v\\|$
$T_{n},S_{n}$	full transformation monoid; symmetric group	$M_{\Phi}$	RNN transition monoid, $M_{\Phi}\coloneq\{\Phi_{w}\mid w\in\Sigma^{*}\}$

Appendix

Table 2: Notation.

Architecture	Recurrence	Transition $A_{t}$	Spectrum
$\rho>1$ : loses contraction, fails (R2) ; realizes nothing. Not targeted in our survey a
$\rho=1$ : loses contraction, fails (R2) ; realizes nothing, $L_{\max}=O(1/\eta)$ for isometries b
linear attention ( Katharopoulos2020 )	$S_{t}=S_{t-1}+\phi(k_{t})v_{t}^{\mathsf{T}}$	$I$	$\{1\}$ , multiplicity $d$
DeltaNet ( Yang2024 )	$S_{t}=S_{t-1}(I-\beta_{t}k_{t}k_{t}^{\mathsf{T}})+\beta_{t}v_{t}k_{t}^{\mathsf{T}}$	$I-\beta_{t}k_{t}k_{t}^{\mathsf{T}}$ , $\beta_{t}=\sigma(\cdot)\in(0,1)$	$\{1^{(d-1)},\,1-\beta_{t}\}$ , $1-\beta_{t}\in(0,1)$
+ negative eigenvalues ( Grazzi2025 )	$H_{t}=(I-2\beta_{t}k_{t}k_{t}^{\mathsf{T}})H_{t-1}+\beta_{t}k_{t}v_{t}^{\mathsf{T}}$	$I-2\beta_{t}k_{t}k_{t}^{\mathsf{T}}$ , $\beta_{t}\in(0,1)$	$\{1^{(d-1)},\,1-2\beta_{t}\}$ , $1-2\beta_{t}\in(-1,1)$
DeltaProduct ( Siems2025a )	$H_{t}=A_{t}H_{t-1}+B_{t}$	$\prod_{j=1}^{n_{h}}(I-\beta_{t,j}k_{t,j}k_{t,j}^{\mathsf{T}})$ , $\beta_{t,j}\in(0,1)$ or $(0,2)$	$1$ with multiplicity $\geq d-n_{h}$

Appendix

Table 3: Surveyed scan-compatible affine architectures, grouped by the branch of Theorem 4.1 . For each, the recurrence as its paper writes it, the transition matrix

A_{t}=A_{x_{t}}

of equation 5 , and its spectrum; keys

k_{t}

and

w_{t}

have unit norm.

Figure 2: Sequential and parallel evaluations of the same model may follow different trajectories. Gap $\|h_{t}^{\mathrm{par}}-h_{t}^{\mathrm{seq}}\|_{\infty}$ between the parallel scan and the sequential recurrence, with the same coefficients $(A_{x_{t}},b_{x_{t}})$ , computed in fp32 and rounded to the format (light: fp32; dark: fp16; complex states stored as two real arrays). Untrained models of width $32$ , $64$ words of length $2^{15}$ over five letters, $5$ seeds. Left: gap at each step (mean over words and seeds; band: range of the per-seed means). Right: distribution over all steps and seeds (whiskers: minimum and maximum). Absolute values are not comparable across models; the trend in $t$ is.

Figure 3: A perfectly trained

\rho=1

recurrence still drifts at finite precision. The exact rotation by

2\pi/7

, which realizes

\mathbb{Z}_{7}

under the constant word, is rounded once to each format and then iterated in fp64 from

h_{0}=(1,0)

. Left: phase error

\Delta\theta_{t}

with respect to the exact run; dashed lines:

\pm\pi/7

, beyond which the readout returns a neighbouring state. Right: log-norm of the hidden state. Crosses mark the first step at which the readout is wrong; every format fails at a finite length, fp32 included.

Task	Monoid	Letters	$\|\Sigma\|$	$\|Q\|$
$\mathbb{Z}_{2}$	cyclic group	residues $0,1$	$2$	$2$
$\mathbb{Z}_{16}$	cyclic group	residues $0,\dots,15$	$16$	$16$
$S_{3}$	symmetric group	adjacent transpositions $(i\;i{+}1)$	$2$	$6$
$S_{4}$	symmetric group	adjacent transpositions $(i\;i{+}1)$	$3$	$24$
$A_{5}$	alternating group	adjacent 3-cycles $(i\;i{+}1\;i{+}2)$	$3$	$60$
$M_{11}$	Mathieu group	$a,\,b,\,a^{-1},\,b^{-1}$	$4$	$7920$

Appendix

Table 4: Algebraic tasks.

|Q|

is the number of reachable states, the order of the monoid.

		Failing length $L_{\max}$ per seed
Task	Model	$42$	$43$	$44$	$45$	$46$	Median	Range
$\mathbb{Z}_{2}$	NFSM	$\geq 1M$	$\geq 1M$	$\geq 1M$	$\geq 1M$	$\geq 1M$	$\geq 1M$	[ $\geq 1M$ ; $\geq 1M$ ]
	Mamba ${}^{\text{---}}$	$4352$	$5176$	$326$	$655$	$\geq 512k$	$4352$	[ $326$ ; $\geq 512k$ ]
	AUSSM	$274$	$115$	$144$	$101$	$151$	$144$	[ $101$ ; $274$ ]
	PD-SSM	$102$	$117$	$105$	$119$	$110$	$110$	[ $102$ ; $119$ ]
$\mathbb{Z}_{16}$	NFSM	$\geq 1M$	$\geq 1M$	$\geq 1M$	$\geq 1M$	$\geq 1M$	$\geq 1M$	[ $\geq 1M$ ; $\geq 1M$ ]

Appendix

Table 5: Seed-to-seed variability of the failing length. For each task and model, the failing length

L_{\max}

of each of the five seeds, and the median and range

[\min;\max]

over the seeds that learned the task; the median is the value reported in Table 1 .

\times

marks a seed that did not learn the task; other notation as in Table 1 .

Figure 4: The state of a trained model on $\mathbb{Z}_{5}$ under the constant word $(+1)^{T}$ , seed $46$ . Each row is a model, each column a window of the same run. Points are the recurrent state projected on its first two principal components, one per step, colored by the target state; the shaded regions are the decision regions of the classifier at the end of the backbone. $B$ is the number of layers of the model.

Task	Heads $(d_{i})$	$\|\Sigma\|$	Joint indices	Reached	Task states
$\mathbb{Z}_{2}$	$(2)$	$2$	$2$	$2$	$2$
$\mathbb{Z}_{16}$	$(16)$	$16$	$16$	$16$	$16$
$S_{3}$	$(3,2)$	$2$	$6$	$6$	$6$
$S_{4}$	$(4,3,2)$	$3$	$24$	$24$	$24$
$A_{5}$	$(5,12)$	$3$	$60$	$60$	$60$
$M_{11}$	$(11,11,11,11)$	$4$	$14641$	$7920$	$7920$

Appendix

Table 6: Extraction on the algebraic tasks. For each task, the head sizes

(d_{i})

, the number of symbols

|\Sigma|

, the number

\prod_{i}d_{i}

of joint indices, the number of joint indices reached from the initial joint index, and the number of reachable task states.

Figure 5: Attractor indices of the heads of a two-layer NFSM reading a

\mathrm{TSO}_{4}

stream. Each row is a head, each column a token of the stream. A head whose attractor indices determine a register of the task is colored by its value, a person or unset; the other heads show their raw index in gray. The box marks the question token, where the answer is read.

Figure 6: Cost of one layer in a training step (forward and backward passes, batch of

16

, one A100). Top left: time per call against the sequence length

L

, at

d=16

; solid lines are the parallel scan, dotted lines the sequential loop. Top right: time per call of the parallel scan against the state size

d

, at

L=2^{12}

. Bottom: peak memory of the parallel scan against

L

, at

d=16

; this is an approximate measurement (see text). Points circled in red are chunked : the sequence is processed in consecutive blocks, which bounds memory at the cost of time.

Finite-State Machine

See all 18 papers

May 8, 2026

Rethinking State Tracking in Recurrent Models Through Error Control Dynamics

The theory of state tracking in recurrent architectures has predominantly focused on expressive capacity: whether a fixed architecture can theoretically realize a set of symbolic transition rules. We argue that equally important is error control, the dynamics governing hidden-state drift along the directions that distinguish symbolic states. We prove that affine recurrent networks, a class of models encompassing State-Space Models and Linear Attention, cannot correct errors along state-separating subspaces once they preserve state representations. Consequently, practical affine trackers do not learn robust state tracking; rather, they learn finite horizon solutions governed by accumulated state-relevant error. We characterize the mechanics of this failure, showing that tracking remains readable only while the accumulating within-class spread remains small relative to the initial between-class separation. We demonstrate empirically on group state-tracking tasks that this breakdown is predictable: tracking collapses when the distinguishability ratio crosses the readability threshold of the trained decoder. Across trained models, the point of this crossing predicts the horizon at which downstream accuracy fails. These results establish that robust state tracking is determined not only by an architecture's theoretical expressivity but crucially by its error control.

Jiwan Chung, Heechan Choi, Seon Joo Kim

Yonsei University

Recurrent Neural Networks State Tracking State Space Models

Ask PDF

Feb 16, 2026

Learning State-Tracking from Code Using Linear RNNs

Over the last years, state-tracking tasks, particularly permutation composition, have become a testbed to understand the limits of sequence models architectures like Transformers and RNNs (linear and non-linear). However, these are often sequence-to-sequence tasks: learning to map actions (permutations) to states, which is incompatible with the next-token prediction setting commonly used to train language models. We address this gap by converting permutation composition into code via REPL traces that interleave state-reveals through prints and variable transformations. We show that linear RNNs capable of state-tracking excel also in this setting, while Transformers still fail. Motivated by this representation, we investigate why tracking states in code is generally difficult: actions are not always fully observable. We frame this as tracking the state of a probabilistic finite-state automaton with deterministic state reveals and show that linear RNNs can be worse than non-linear RNNs at tracking states in this setup.

Julien Siems, Riccardo Grazzi, Korbinian Pöppel +3

University of Freiburg · Prior Labs · Microsoft Research +2

Recurrent Neural Networks State Tracking Linear RNNs Sequence Modeling

Ask PDF

Jun 5, 2026

A Held-Out Transition-Pair Falsifier for Long-Horizon Non-Abelian State Tracking

State tracking exposes a sharp limitation of sequence models: the relevant signal is often not a summary of observed tokens, but an ordered latent state that evolves through non-commutative transformations. We introduce a held-out transition-pair falsifier for finite non-Abelian group tracking. The protocol forbids selected ordered generator pairs during training and requires the same local patterns during evaluation, blocking one direct local-transition memorization pathway. In a controlled

S_3 \times S_3

benchmark, a projected recurrent state model trained only on length-8 sequences produces error-free final-state predictions (perfect 250/250 per horizon) through evaluation horizons up to 1,048,576 tokens across five seeds. Matched native-readout baselines, including bag, GRU, and a single-configuration structured state-space model, remain near floor under the same protocol. Projection-matched GRU, structured SSM, and bag baselines equipped with analogous finite-group prototype readouts also remain near chance under the same split. Mechanism diagnostics show that hard projection coincides with low homomorphism error, low state-consistency drift, and non-trivial commutator separation, while softened projection collapses final-state accuracy. Clean-split audits verify zero verbatim reduced-word overlap and zero structural-template overlap between training and evaluation partitions. The evidence is scoped to this controlled finite-group falsifier rather than to a general architecture ranking. Within that regime, explicit projected non-commutative state composition acts as a useful inductive bias for long-horizon hidden-state tracking.

Jeonghoon Lee

Attractor Dynamics

Recurrent Neural Networks State Tracking Sequence Modeling

Ask PDF

Abstract

Finite-State Machine

Explore similar work

Rethinking State Tracking in Recurrent Models Through Error Control Dynamics

Learning State-Tracking from Code Using Linear RNNs

A Held-Out Transition-Pair Falsifier for Long-Horizon Non-Abelian State Tracking