💬 NLP

Rethinking State Tracking in Recurrent Models Through Error Control Dynamics

This paper argues that robust state tracking in recurrent models depends critically on error control dynamics rather than just theoretical expressivity, demonstrating that affine recurrent networks inevitably fail at long-horizon tasks because their inability to correct state-separating errors leads to predictable tracking collapse once accumulated within-class spread exceeds the decoder's readability threshold.

Original authors: Jiwan Chung, Heechan Choi, Seon Joo Kim

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiwan Chung, Heechan Choi, Seon Joo Kim

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to keep a mental tally of a complex game, like tracking who is currently "in charge" in a board game where players constantly swap roles. You have a notebook (your brain's hidden state) where you write down the current status. Every time a new move happens, you update your notebook.

For a long time, scientists believed the only thing that mattered for a computer to do this was expressivity: "Does this computer have a big enough notebook and a smart enough pen to theoretically write down every possible rule of the game?"

This paper argues that expressivity is only half the story. The other, more critical half is error control. It's not just about having the right rules; it's about what happens when you make a tiny mistake.

The Core Problem: The "Drifting" Notebook

Imagine you are walking a tightrope. If you take a perfect step, you stay on the line. But in the real world, you might wobble slightly.

The Ideal Tracker: If you wobble, you have a built-in mechanism (like a balancing pole) that instantly corrects your balance and pulls you back to the center.
The Flawed Tracker: If you wobble, you just keep wobbling. You don't fall off immediately, but with every step, your wobble gets slightly bigger. Eventually, you drift so far off the line that you can no longer tell which side of the rope you are on.

The authors found that many popular modern AI models (like Mamba and Linear Attention) are the second type. They are mathematically capable of knowing the rules, but they lack the "balancing pole" to fix small mistakes.

The "Affine" Trap

The paper focuses on a specific class of models called Affine Recurrent Networks. Think of these as models that update their memory using a very rigid, straight-line formula.

The Rule: If the model is perfect, it must return to the exact same spot every time the game cycle repeats.
The Catch: Because the formula is so rigid (affine), if it is forced to return to the exact same spot, it loses the ability to pull itself back if it drifts away. It's like a car with a steering wheel that is locked straight. If the car is perfectly centered, it drives fine. But if a pebble nudges it slightly off-center, the car cannot steer back; it just keeps driving in a straight line, getting further and further from the center.

The paper proves that once these models learn the rules perfectly, they become "neutral" to errors. They preserve the state, but they cannot correct the drift.

The "Finite Horizon" Effect

So, do these models fail immediately? No.
Think of it like a leaky bucket.

If you are walking a short distance (a short sequence of text), the leak is so slow that you don't notice. The bucket still holds enough water to tell you the answer.
But as you walk further (longer sequences), the water (accuracy) slowly drains away.
Eventually, the bucket is so empty (or the water so murky with errors) that you can no longer distinguish the "right" answer from the "wrong" one.

The paper calls this the Finite Horizon. These models work fine for a while, but they have a hard limit. Once the accumulated "noise" or "drift" becomes larger than the gap between the correct answer and the wrong answer, the model collapses.

The Solution: The "Balancing Pole" (State-Dependence)

The paper compares these rigid models to State-Dependent Models (like standard RNNs with non-linear activations).

These models are like a cyclist with a balancing pole. If they wobble, the cyclist can actively steer back.
Mathematically, this means the way they update their memory changes depending on where they currently are. If they are drifting, the update rule changes to push them back.
The experiments show that these models can walk the tightrope forever, no matter how long the sequence gets, because they actively fix their own mistakes.

The "Readability" Threshold

The authors developed a way to predict exactly when the rigid models will fail.
Imagine the correct answers are distinct islands in a foggy ocean.

Separation: The distance between the islands.
Spread: How foggy the water is around each island (caused by accumulated errors).
The Tipping Point: As long as the fog (error spread) is smaller than the distance between islands, you can still see which island you are on. But once the fog gets thicker than the distance between the islands, you can no longer tell where you are.

The paper shows that for rigid models, this fog grows predictably. They can calculate exactly how many steps it will take before the fog becomes too thick, and this prediction matches exactly when the model stops working in practice.

Summary of Findings

Theory isn't enough: Just because a model can theoretically represent a rule doesn't mean it can use that rule reliably over time.
Rigid models drift: Models that use simple, straight-line updates (Affine) cannot fix their own small errors. They preserve the state perfectly only if they start perfectly.
The limit is predictable: These models don't fail randomly; they fail when the accumulated error overtakes the distance between the correct answers.
Flexibility wins: Models that can change their update rules based on their current state (State-Dependent) can actively correct errors, allowing them to track information indefinitely.

In short: Robustness isn't about how smart your map is; it's about how well your compass corrects you when you take a wrong step.

Technical Summary: Rethinking State Tracking in Recurrent Models Through Error Control Dynamics

Problem Statement

The prevailing theoretical framework for state tracking in recurrent architectures has focused almost exclusively on expressivity: determining whether a fixed architecture can theoretically realize a set of symbolic transition rules. While recent works have established the theoretical capacity of various models (e.g., State-Space Models, Linear Attention) to represent specific symbolic transitions, empirical results show a significant gap between theoretical expressivity and practical robustness. Models often fail to track states stably under length extrapolation or repeated rollout, even when they possess the theoretical capacity to do so.

This paper argues that error control—the dynamics governing hidden-state drift along directions that distinguish symbolic states—is an equally critical, yet overlooked, axis of analysis. The central problem is that theoretical expressivity does not guarantee the ability to correct accumulated errors that push a hidden state toward an incorrect symbolic representation.

Methodology

Theoretical Framework

The authors formalize state tracking using a taxonomy of recurrent models defined by a recursive layer:
$h_t = \phi(g(h_{t-1}, x_t) \odot (A(x_t)h_{t-1})) + b(x_t)$
They categorize models into two primary classes based on the state Jacobian:

Affine Models: The state transition is affine in $h_{t-1}$ (i.e., the Jacobian $\partial h_t / \partial h_{t-1}$ does not depend on $h_{t-1}$ ). This class includes State-Space Models (SSMs) like Mamba, AUSSM, and Linear RNNs.
State-Dependent Models: The transition depends non-linearly on the current state (e.g., gated RNNs, tanh RNNs).

The authors introduce a symbolic subspace $U$ , spanned by the differences between hidden-state representations of distinct symbolic states ( $U := \text{span}\{c_g - c_{g'}\}$ ). They prove that for any state-preserving sequence (where the symbolic action is the identity), an exact affine return map must act as the identity on $U$ . Consequently, affine models cannot contract errors along $U$ ; they preserve the state representation exactly but offer no mechanism to pull a perturbed state back to its correct centroid.

Analytical Metrics

To quantify the failure of affine trackers, the authors define a distinguishability ratio $q(t)$ :
$q(t) = \frac{R(t)}{M(t)}$
Where:

$R(t)$ is the within-class spread (variance of hidden states around their class centroid).
$M(t)$ is the between-class separation (minimum distance between class centroids).
$q(t)$ measures the spread relative to the margin.

They establish that tracking remains "readable" only while $q(t)$ stays below a threshold $\tau$ (specifically $0.5$ for a nearest-centroid decoder).

Experimental Setup

The authors evaluate a spectrum of recurrent architectures on group state-tracking tasks, which require maintaining a running product of group elements:

Tasks: Parity ( $C_2$ ), Cyclic Group ( $C_6$ ), and Symmetric Group ( $S_3$ ). $S_3$ is non-Abelian, making order-sensitive composition unavoidable.
Models: A diverse set including Mamba, Mamba-3, AUSSM, Negative Mamba, Linear RNNs, Token-gated RNNs, tanh RNNs, and State-gated RNNs.
Protocol: Models are trained with curriculum learning up to length 60 and evaluated for extrapolation up to length 1000. They also perform perturbation injection experiments to measure error recovery dynamics.

Key Contributions

1. Theoretical Proof of Affine Neutrality

The paper proves Theorem 1: If an affine recurrent network preserves symbolic states exactly, its return map acts as the identity on the symbolic subspace $U$ . This implies that affine models cannot selectively contract errors along the directions that separate symbolic states. Once a state-preserving affine map is fixed, it has no "degrees of freedom" left to correct drift.

2. Characterization of Finite-Horizon Failure

The authors demonstrate that while affine models cannot correct errors, they can sustain tracking for a finite horizon governed by accumulated error.

Corollary 1 shows that for approximate affine trackers, the error along $U$ accumulates linearly over time ( $e_U(t) \approx e_U(0) + t\bar{\eta}$ ).
Tracking collapses when the distinguishability ratio $q(t)$ crosses the readability threshold. This crossing time, $T_{cross}$ , quantitatively predicts the maximum passing length ($mp$) of the model.
Two failure modes are identified: Saturation (where $q(t)$ starts above the threshold) and Climb (where $q(t)$ grows linearly until crossing).

3. Empirical Validation of Error Control Dynamics

Through extensive experiments, the paper establishes a dichotomy:

State-dependent models (e.g., tanh RNN, State-gated RNN) exhibit conditional error contraction. They can selectively shrink perturbations along $U$ , maintaining $q(t) < 0.5$ indefinitely and achieving robust tracking up to the maximum tested length (1000).
Affine models lack this selective contraction. They either fail immediately (saturation) or fail after a predictable horizon (climb) as accumulated within-class spread erodes the separation margin.

4. Subspace Decomposition

By decomposing the within-class spread into components parallel ( $U$ ) and orthogonal ( $U^\perp$ ) to the symbolic subspace, the authors show that affine model failure is specifically driven by the growth of spread within $U$ . State-dependent models successfully suppress spread in $U$ , keeping errors in the orthogonal subspace where they do not affect symbolic discrimination.

Results

Robustness Gap: State-dependent models consistently track symbolic states up to length 1000 across all tasks ( $C_2, C_6, S_3$ ). In contrast, affine models show varying degrees of instability. For instance, Mamba and Mamba-3 fail on $S_3$ even at short lengths, while Negative Mamba and Token-gated RNNs show extended horizons on $C_2$ and $S_3$ but eventually collapse.
Predictive Power: The point at which the distinguishability ratio $q(t)$ crosses the readability threshold ( $T_{cross}$ ) strongly correlates ( $r \approx 0.87$ ) with the downstream maximum passing length ($mp$) across 113 trained models.
Nonlinearity Matters: The ability to track robustly depends on the activation function's Jacobian being state-dependent. Pointwise nonlinearities (tanh, ReLU) and pair operators (max/min, GroupSort) enable robust tracking, whereas whole-vector normalizations (LayerNorm, sphere projection) fail, behaving effectively as affine maps on the symbolic subspace.
The $C_2$ Edge Case: The paper notes that some affine models succeed on the parity task ( $C_2$ ) not because they correct errors, but because the binary margin is large enough to tolerate "neutral oscillation" (errors flipping sign but staying within the margin). This tolerance shrinks as the group order increases, explaining why affine models fail on $C_6$ and $S_3$ .

Significance and Claims

The paper claims to shift the paradigm of recurrent state tracking from a theory of expressivity to a theory of error control.

Theoretical Limitation: The authors assert that robust state tracking is not solely determined by an architecture's ability to represent symbolic rules (expressivity) but crucially by its ability to control error dynamics. Affine models are fundamentally limited because preserving state representations forces them to be neutral on the very directions where error correction is needed.
Practical Implication: The failure of affine models (like SSMs) in length extrapolation is not a training deficiency but a structural limitation. They learn "finite horizon solutions" governed by accumulated error rather than robust, infinite-horizon state tracking.
Design Guidance: To achieve robust tracking, architectures must incorporate state-dependent transitions that allow the Jacobian to contract errors along the symbolic subspace. The paper suggests that the specific form of nonlinearity is less important than whether it enables state-dependent modulation of the symbolic directions.

The authors conclude that while affine models may be sufficient for in-domain tasks or short horizons, they are structurally incapable of the robust, long-horizon state tracking required for complex symbolic reasoning without state-dependent error correction mechanisms.