PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking State Tracking in Recurrent Models Through Error Control Dynamics

Jiwan Chung, Heechan Choi, Seon Joo Kim

arXiv:2605.07755v1cs.LGcs.CL

TL;DR

State-tracking theory has emphasized expressive capacity, while robust long-horizon tracking also depends on controlling hidden-state errors. This paper analyzes error dynamics in affine and state-dependent recurrent models, showing that affine tracking breaks down when accumulated state-relevant error crosses the decoder’s readability threshold.

  • Problem

    State-tracking research has emphasized whether architectures can represent symbolic transitions, leaving error control during repeated reuse comparatively underexamined.

  • Method

    The paper proves affine models cannot correct state-separating drift, characterizes finite-horizon readability, and evaluates distinguishability-threshold diagnostics on group tracking tasks.

  • Results

    The readability-threshold crossing quantitatively predicts downstream failure horizons across affine sweeps, while state-dependent models sustain tracking over the longest tested horizons.

  • Takeaways & Limitations

    Robust state tracking depends crucially on error control dynamics in addition to theoretical expressivity.

  • Takeaways & Limitations

    C2 is an order-two edge case that tests margin-tolerated neutral transport rather than active correction of state-subspace drift.

Abstract

from arXiv · show

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.

1 Introduction

The paper reframes recurrent state tracking around error control: affine models cannot correct state-separating drift once they preserve state representations, so their tracking is finite-horizon. Robustness depends on error dynamics as well as theoretical expressivity, with distinguishability predicting when accumulated spread makes states unreadable.

  • Motivation: State-tracking theory has emphasized which symbolic transition rules architectures can realize, but the paper identifies hidden-state drift along state-separating directions as an equally important error-control problem.The paper frames error control as the dynamics governing hidden-state drift along directions that distinguish symbolic states.
  • Motivation: Prior results and the paper’s motivation show that models sufficient for symbolic tasks can still track unstably under repeated rollout or collapse when extrapolating beyond training lengths.The cited examples include complex-diagonal and diagonal selective SSM variants, as well as failures within an architecture’s claimed task scope.
  • Core mechanism: Affine recurrent models cannot correct symbolic-state drift once they preserve state representations, whereas state-dependent return maps can selectively contract drift in symbolic subspaces.The paper also verifies which canonical activations realize this correction.
  • Empirical evaluation: On group state-tracking tasks, state-dependent models maintain tracking over the longest tested horizons, while affine models lose accuracy at different horizons.The variation among affine failure horizons is central: models differ in how long they sustain tracking under repeated recurrence.
  • Diagnostics: The distinguishability ratio q(t) = R(t)/M(t) captures affine trackers’ finite horizon as within-class spread approaches between-class separation, while perturbation recovery reveals selective contraction only in state-dependent models.The diagnostics provide a consistent error-dynamics explanation for gradual tracking failure rather than necessarily immediate failure.

2 Background

This section defines recursive layers through latent-state updates and distinguishes recurrent model classes by their transport, injection, modulation, and activation components. It also formalizes state tracking as online recovery of symbolic states, including group-based running-product tasks.

  • Recursive layers: A recursive layer maps an input sequence to outputs while maintaining a d-dimensional latent state h_t.The layer is introduced as a parametrized recurrence over inputs x_t, with hidden state h_t ∈ F^d.
  • Recursive layers: The recurrence separates state transport A(x_t)h_{t−1}, input injection b(x_t), state-dependent modulation g(h_{t−1},x_t), and output activation ϕ.Constraining or removing these ingredients yields different recurrent model classes.
  • State tracking: State tracking requires an online model to maintain enough hidden-state information to recover the evolving symbolic state g_t at every step.The symbolic trajectory follows g_t = T(g_{t−1},x_t) over a finite state space and transition rule.
  • Group state-tracking tasks: Finite-group tasks evaluate tracking through running products, with cyclic groups testing modular counting and symmetric groups testing order-sensitive, non-Abelian composition.For group inputs, the target is y_t = x_1 · x_2 · · · x_t; S_k is non-Abelian for k ≥3, making S_3 the smallest order-sensitive case.

3 Error control in state tracking

Robust state tracking requires controlling hidden-state errors along the directions separating symbolic states, not merely preserving clean state representations. For affine return maps, exact preservation prevents correction in those directions, so readability becomes a finite-horizon problem governed by accumulated error.

  • Error control: Robust tracking must correct hidden-state perturbations that move representations toward competing symbolic states, because these directions define symbolic discrimination.Exact realization on clean trajectories alone is insufficient for long-horizon tracking.
  • Affine error dynamics: Once an affine return map fixes every symbolic representation exactly, it cannot shrink the state-separating subspace or create a restoring attractor there.Theorem 1 establishes this neutrality for non-degenerate representations and state-preserving sequences.
  • State-dependent correction: State-dependent return maps can instead make nearby symbolic-subspace errors contract when their local Jacobians have norm uniformly below one.State dependence permits, but does not guarantee, state-conditioned correction.
  • Finite-horizon readability: Symbolic states remain readable while q(t) < τ, where q(t) measures decoder-visible within-class spread relative to between-class separation.R(t) is the within-class spread, M(t) the between-class separation, and τ = 1/2 under the nearest-centroid bound.
  • Finite-horizon readability: Tcross ≈ τM ∥Wout¯η∥ predicts when coherent state-relevant residual errors make distinguishability cross the readability threshold.Affine models exhibit either immediate saturation above τ or a linear climb from below until the crossing.

4 Experiments

Experiments show that state-dependent recurrent models robustly track symbolic states, while affine models exhibit finite-horizon behavior governed by error accumulation and the shift of spread into state-separating directions. The first distinguishability-bound crossing strongly predicts downstream tracking failure.

  • Tracking robustness: State-dependent models track C2, C6, and S3 through 1000 tokens, whereas affine models are generally unstable, with exceptions including Negative Mamba and Token-gated RNN.All models except Mamba can solve the three tasks with two layers, indicating that the robustness gap is not explained by expressivity alone.
  • Tracking robustness: Negative Mamba reaches 1000 on C2, while Token-gated RNN reaches 1000 on C2 (L1) and S3 (L2), but only 500 on S3 (L1) and 400 on C6 (L2).These results show that affine dynamics can approximate correction over finite horizons, including beyond the 60-token training length.
  • Error-control dynamics: State-dependent models contract injected perturbations by several orders of magnitude, whereas affine SSMs globally dissipate errors and Token-gated RNN amplifies them.Affine SSM decay follows global diagonal factors α_t = exp(∆tA), while token-only gates make clean and perturbed rollouts share the same gates.
  • Readability dynamics: Affine trajectories eventually cross the nearest-centroid bound: Mamba and Mamba-3 begin saturated, while Negative Mamba and Token-gated RNN remain readable before accumulated defects force a crossing.Token-gated RNN grows spread with separation, whereas Negative Mamba directly bounds spread and therefore climbs more slowly.
  • Readability dynamics: For Negative Mamba and Token-gated RNN, spread initially lies mostly in U⊥ but shifts into U near maximum passing length; state-dependent models suppress q_U.U denotes the state-separating subspace where affine return dynamics cannot generically contract errors.
  • Predicting failure: r = +0.87, p < 10^-30: across 113 S3 models, T_cross strongly correlates with downstream maximum passing length.Empirical failure aligns closer to q_t = 1 than the sufficient nearest-centroid bound q_t < 0.5; at t = m_p, median q_t is 0.91 with 95% bootstrap CI [0.83, 1.07].

5 Conclusion · Appendix Overview

The conclusion argues that robust recurrent state tracking requires controlling accumulated errors, not merely representing symbolic transitions. The appendix provides related work, implementation details, further discussion, additional empirical results, task examples, and model descriptions.

  • 5 Conclusion: Robust recurrent state tracking requires controlling errors accumulated through repeated state reuse, beyond architectural expressivity.The conclusion frames expressivity as incomplete without error control.
  • 5 Conclusion: Affine models cannot correct errors on state-separating subspaces while preserving the symbolic state representations.The conclusion attributes this limitation to identity action on directions separating symbolic states.
  • 5 Conclusion: Approximate affine trackers fail when accumulated error overtakes the state margin.The supplied conclusion passage identifies accumulated error relative to the state margin as the failure condition.
  • Appendix Overview: Appendix section B presents related work.
  • Appendix Overview: Appendix section C presents implementation details.
  • Appendix Overview: Appendix section E presents further discussions.
  • Appendix Overview: Appendix section F presents additional empirical results.
  • Appendix Overview: Appendix sections G and H provide state tracking task examples and model descriptions, respectively.

A Limitations · B Related Work · C Experimental Detail

The study isolates error control in recurrent symbolic state tracking, while delimiting its claims to finite-group recurrent settings and reporting related expressivity work and experimental procedures. It excludes attention baselines, documents substantial compute and statistical conventions, and provides code and asset disclosures.

  • A Limitations: Affine return maps cannot provide state-dependent error dynamics to preserve symbolic-state separation when states must be reused beyond the training horizon.This limitation does not imply that affine recurrences fail in-domain or are unsuitable for sequence modeling generally.
  • A Limitations: Experiments focus on finite-group tracking, using C2, C6, and S3, with appendix extensions to C2×C4 and A4 across five groups.The affine/state-dependent dichotomy persists across all five tested groups.
  • A Limitations: Attention-based baselines are excluded because the study targets recurrent state-update models and their length-generalization behavior.Attention-based models are outside the scope of this recurrent state-tracking study.
  • B Related Work: Prior work spans nonlinear gated RNNs and scalable linear recurrent architectures, including LRU’s diagonal dynamics and DeltaNet’s linear recurrence.Elman RNNs introduced basic nonlinear tanh updates, while LSTM and GRU addressed vanishing gradients with gating.
  • B Related Work: Expressivity analyses place common linear SSMs in L-uniform TC0 and identify spectral conditions needed for parity and periodic state tracking.Prior work also extends expressivity analysis to non-diagonal linear recurrent models.
  • B Related Work: AUSSM can simulate Abelian groups, including cyclic groups, while single-layer input-dependent complex-valued diagonal SSMs have documented state-tracking limits.Karuvally et al. combine AUSSM with Mamba for solvable group recognition; Shakerinava et al. study DCD SSM expressivity.
  • C Experimental Detail: Training and analysis use one NVIDIA RTX A6000 or 3090 GPU per run, with recurrent stacks requiring 0.10–0.40 GPU-hours per cell.The full sweep covers 81 cells × 9 models × 3 groups × 2 depths and totals at most ∼2,000 GPU-hours.
  • C Experimental Detail: Aggregated curves report medians over N = 200 rollouts with per-step IQR bands, while perturbation-recovery panels use n = 200 injection trials.The Tcross correlation includes a Pearson coefficient, p-value, and a 95% bootstrap confidence interval on the median qt at t = mp.

C.1 Training and grid search … D.2 Proof of perturbation neutrality

The paper trains and evaluates recurrent state trackers through a fixed curriculum, grid-search protocol, and diagnostic probes of error correction and state separation. Its affine proof shows that exact state preservation makes perturbations in the state-separating subspace persist unchanged.

  • C.1 Training and grid search: All models use the canonical recurrent layer in a pre-norm residual block, width dmodel = 698, linear readout, uniformly sampled group sequences, and cross-entropy training.Inputs are token sequences x1, …, xT from G, with predictions of the running product at every step.
  • C.1 Training and grid search: The curriculum begins at T = 2, doubles after test accuracy exceeds 0.95 for five consecutive epochs, and stops at Lmax = 60.Each stage regenerates 10 000 training sequences and 2 000 test sequences; optimization uses AdamW with weight decay 0.01 and batch size 256.
  • C.1 Training and grid search: Frozen models are evaluated on 2 000 fresh sequences at lengths 100 through 1000, with mp defined as the largest length achieving test accuracy at least 0.90.If no generalization length passes after reaching Lmax = 60, mp = 60; nonconvergent curricula receive mp = 0 and are printed as ✗.
  • C.1 Training and grid search: The grid searches (dstate, lr, scheduler, seed), and selects the checkpoint lexicographically maximizing (mp, final_test_acc), recording its seed for reproducible diagnostics.The reported state-tracking number in each Table 2 cell is mp for the grid-best checkpoint, with no additional hyperparameters introduced.
  • C.2 Per-experiment specification: The error-correction probe injects Gaussian noise with σ = 10−2 at t0 = 20 into the first block’s recurrent operator state and tracks normalized perturbation growth.It uses N = 200 fresh S3, L = 1 sequences of length T = 200; the reported contraction rate is derived from the median final error ratio.
  • C.2 Per-experiment specification: State-separation diagnostics evaluate N = 200 fresh S3, L = 1 rollouts to Tmax = 1500, reporting readout-space R(t), M(t), and q(t) curves with latent overlays.Vertical markers reproduce each model’s mp from Table 2, while centroids are computed by grouping rollouts according to oracle symbols.
  • C.2 Per-experiment specification: The symbolic-subspace analysis uses the top k = |G| −1 right singular vectors of the centered centroid matrix and decomposes within-class deviations into symbolic and complementary components.The complementary component is computed without materializing the d×d projector, then aggregated across rollouts as root-mean-square quantities.
  • D.1 Proof of Theorem 1: For an affine, state-preserving return map Fs(h) = Ash + bs, exact preservation fixes every centroid and forces As to act as the identity on the state-separating subspace U.Because centroid differences span U, the proof establishes As|U = I.

D.3 Proof of Corollary 1 · E Further Discussions

The proof shows that exact affine state-preserving dynamics do not contract state-separating deviations, so approximation residuals accumulate rather than being corrected. With coherent residual drift, readout-visible error grows until it overwhelms stable between-state separation, determining a finite tracking horizon.

  • D.3 Proof of Corollary 1: Exact affine state-preserving dynamics have no contracting homogeneous component along directions that distinguish symbolic states.Along a return cycle, the state representation is preserved, so the corresponding state-subspace dynamics cannot contract these directions.
  • D.3 Proof of Corollary 1: The trained tracker’s projected deviation evolves through the exact affine return map plus a projected approximation residual.The recurrence separates the propagated current deviation from the approximation error introduced at the update.
  • D.3 Proof of Corollary 1: Because the exact affine part preserves state-subspace deviations, it does not reduce the current deviation within the projected dynamics.Restricting the dynamics to U gives A_s|_U = I, so the state-relevant deviation is maintained rather than contracted.
  • D.3 Proof of Corollary 1: Unrolling the recurrence shows that projected residuals are accumulated, not corrected, by the affine return dynamics.The additive residual terms persist across successive returns because the state-subspace dynamics do not contract them.
  • D.3 Proof of Corollary 1: Linear error growth arises when residuals contain a coherent component over the relevant horizon, rather than from the recurrence identity alone.The recurrence establishes additive entry of residuals; coherent alignment is the additional condition producing linear accumulation.
  • D.3 Proof of Corollary 1: The readout-visible error eventually scales with the coherent drift, while the fixed initial error becomes lower order.The growing component has scale determined by the readout projection of the coherent residual direction.
  • D.3 Proof of Corollary 1: Tcross ≈ τM ∥Wout¯η∥.When between-state separation remains approximately stable at M(t) ≈ M > 0, the crossing scale is set by the separation divided by readout-visible drift.
  • D.3 Proof of Corollary 1: The finite horizon is controlled by the competition between stable separation M and coherent readout-visible drift ∥Wout¯η∥.Tracking remains readable only until accumulated drift crosses the scale set by between-state separation.

E.1 Per-operator Jacobian analysis

Per-operator Jacobian analysis shows that robust state tracking depends on whether the activation Jacobian encodes state-dependent, per-direction transformations on the symbolic subspace U. Pointwise and pair operators can provide contraction, whereas whole-vector normalizations cannot distinguish U directions sufficiently.

  • Jacobian criterion: State-dependent error correction requires the return-map Jacobian on U to have norm strictly below one uniformly over centroids.The activation ϕ determines whether the return map can vary its Jacobian with state.
  • Jacobian criterion: The ability to contract along U across different centroids depends entirely on ∂ϕ/∂p.Here U = span{cg − cg′} is the symbolic subspace separating state representations.
  • Pointwise activations: Pointwise scalar activations such as tanh and ReLU yield state-dependent diagonal Jacobians that can contract U differently at different centroids.For tanh, the diagonal entries are 1 − tanh^2(pt); for ReLU, they are 1[pt > 0].
  • Pair operators: Pair operators such as max, min, and GroupSort with k = 2 provide state-dependent permutations that mix U directions differently across centroids.Their Jacobians are permutation matrices varying with ht, while each linear region remains 1-Lipschitz.
  • Whole-vector normalizations: Whole-vector normalizations behave nearly like the identity on U and cannot provide fixed-margin, per-direction contraction when d ≫ |G|.LayerNorm contributes only O(1/d) direction-specific effects, while sphere projection acts as an isotropically scaled orthogonal projector.

E.2 The C2 edge case · F Additional empirical results · F.1 Additional models

C2 can appear robust because neutral oscillations remain within its wide binary readout margin, but this is not genuine state-subspace error correction. Additional-model results further show that learned solutions need not realize an architecture’s full theoretical expressivity.

  • E.2 The C2 edge case: C2 is the only group where several affine models, notably Negative Mamba and Token-gated RNN, reach the maximum tested length.This success reflects C2’s tolerance of persistent sign-flipping errors within the binary readout margin, not genuine correction.
  • E.2 The C2 edge case: In C2, state-subspace perturbations can oscillate without contraction while nearest-centroid decoding remains correct inside the readout margin.A state-preserving affine return word acts as the identity on the perturbation subspace, so the error is transported rather than corrected.
  • E.2 The C2 edge case: Neutral-oscillation tolerance decreases as cycle order grows because the angular decision sector narrows and phase errors become easier to misclassify.The tolerated phase error is π/k, making the C2 margin advantage unusually large.
  • F Additional empirical results: Table 5 extends the empirical comparison beyond the main table to additional existing architectures.The extension examines PD-SSM, DeltaNet, and DeltaProduct alongside the models from Table 2.
  • F.1 Additional models: The additional-model results show that learned solutions need not realize the full expressivity available to their architectures.This finding motivates distinguishing architectural expressivity from the behavior actually learned during state tracking.
  • E.2 The C2 edge case: Median return-word gain near 1 for Negative Mamba and Token-gated RNN on C2 indicates neutral transport rather than contraction.Gain > 1 indicates amplification, whereas gain < 1 may reflect centroid collapse or genuinely state-dependent correction.
  • F.1 Additional models: The reported additional architectures are PD-SSM, DeltaNet, and DeltaProduct, evaluated alongside the models from Table 2.These models are absent from the main table and are introduced in the extended comparison.

F.2 Additional tasks · F.3 Statistical significance · F.4 Preliminary and discarded experiments

Additional tasks on C2 × C4 and A4 showed trends consistent with the main results, while statistical analyses quantified rollout variability at representative evaluation steps. Preliminary experiments explored discarded recursive variants and alternative perturbation settings before the reported configurations were fixed.

  • F.2 Additional tasks: Table 6 extends the evaluation to the abelian group C2 × C4 and the non-abelian alternating group A4.Both additional tasks were evaluated on tanh RNN, State-gated RNN, Token-gated RNN, Negative Mamba, and Mamba-3.
  • F.3 Statistical significance: Figure 3 and Figure 1 report per-step medians with IQR bands over N = 200 rollouts.Table 7 reports median, Q1–Q3, and max at a single representative step teval using the same grid-best checkpoints.
  • F.3 Statistical significance: The reported metrics measure latent RMS error relative to minimum class-pair separation and unprojected perturbation error relative to its initial value.The definitions are rerr,U/rsep for latent error and ∥e∥/∥et0∥ for unprojected per-rollout error.
  • F.3 Statistical significance: teval is set to the model’s max-passing length mp when the task was learned, or curriculum length 60 when mp = 0.This avoids evaluating divergent runs beyond the point where figure trajectories overflow.
  • F.2 Additional tasks: Both additional tasks exhibit trends consistent with the main results.This extension is reported in Table 6 alongside the original task evaluations.
  • F.4 Preliminary and discarded experiments: Preliminary experiments used comparable compute but were excluded from the paper, including early recursive-model variants later discarded after final operator forms and the modular taxonomy were fixed.These variants were discarded because they introduced irrelevant confounds.
  • F.4 Preliminary and discarded experiments: The project also tested alternative Figure 1 perturbation-injection settings, varying magnitude and injection point before fixing the reported setup.The supplied passage identifies these as preliminary experiments not included in the paper.

G Examples of State Tracking Tasks … H.2 Recurrent Networks

The paper defines state-tracking tasks through modular and permutation-group transitions, then maps recurrent architectures to a canonical form that distinguishes affine transport from state-dependent updates. Minimalist constructions track C2, C3, and S3 states using sign, complex phase, and layered representations, while model details classify the recurrent and state-space families by their transition geometry and gating.

  • G.1 Parity (C2): Parity tracking is modulo 2 counting in C2, with each input updating the state by gt = gt−1 + xt (mod 2) and producing the running sum modulo 2.For the sequence 1, 1, 0 from g0 = 0, the states are g1 = 1, g2 = 0, and g3 = 0.
  • G.1.1 Sketch of an Affine Recurrent Model for Tracking C2: A minimalist one-dimensional affine tracker represents C2 with ht ∈{1, −1}, inverting its sign whenever xt = 1 through an input-dependent transition.The construction initializes h0 = 1 and uses the negative eigenvalue −1 to alternate between the two group states.
  • G.2 Cyclic Group (C3): Cyclic-group tracking generalizes to modulo k counting; for C3, gt = gt−1 + xt (mod 3) and the task outputs the running sum modulo 3.For the sequence 1, 2, 1 from g0 = 0, the states are g1 = 1, g2 = 0, and g3 = 1.
  • G.2.1 Sketch of an Affine Recurrent Model for Tracking C3: A minimalist complex-valued affine tracker represents C3 with phase shifts of 120° multiplied by xt, using the third roots of unity on the unit circle.The final states hT = 1, hT = e^j2π/3, and hT = e^j4π/3 encode modulo-3 sums 0, 1, and 2, respectively, without exponential decay or explosion.
  • G.3 Symmetric Group (S3): S3 is the smallest non-Abelian symmetric group, with six elements, and reversing the order of generators (12) and (23) yields different final states.This order dependence demonstrates that S3 is non-commutative.
  • G.3.1 Sketch of an Affine Recurrent Model for Tracking S3: The proposed two-layer affine model tracks S3 by decomposing each token into C2 and C3 indicators, combining a real parity tracker with a C2-conditioned complex rotational accumulator.The layer-state combinations provide a bijective, unambiguous mapping to all six S3 elements.
  • H Model Details: The experiments map models to a canonical recurrent form and span diagonal contractive, signed diagonal, damped complex rotation, unitary, dense linear, nonlinear, input-gated, and state-gated families.This comparison isolates affine versus state-dependent transitions while allowing at most one scoped canonical-form violation per model.
  • H.1 State-Space Models: State-space models are classified by transition geometry, while recurrent networks range from constant dense transport to input-only or state-and-input gating, with nonlinearities or additional coupled and matrix-valued states marking canonical-form deviations.S4 is time- and input-invariant; Mamba is diagonal contractive; Negative Mamba is signed diagonal; Mamba-3 uses damped complex rotation; AUSSM variants are unitary; Linear RNN, tanh RNN, Token-gated RNN, and State-gated RNN provide recurrent-network counterparts.
Loading 2605.07755v1…