Linear RNNs Outperform Transformers at Tracking State Changes in Code

A new study on arXiv examines how different neural architectures handle state-tracking problems when embedded in code execution. The research bridges a longstanding gap in how we evaluate sequence models: most state-tracking benchmarks work as pure sequence-to-sequence tasks, but language models learn in a next-token prediction framework.

From Permutation Tasks to Code#

The researchers converted the classic state-tracking problem of permutation composition into Python REPL traces—executable code that interleaves variable assignments with print statements that "reveal" the current state. This creates a more realistic setting where models must predict the next token while implicitly maintaining an internal representation of program state.

Results Show Linear RNNs Advantage#

Linear RNNs—relatively simple recurrent models without nonlinearity—proved capable of tracking states in this code-based setting, while Transformers failed at the task. This finding suggests that the inductive biases of linear RNNs align well with systematic state evolution.

The Complexity of Partial Observability#

The work goes deeper by investigating why state tracking in code is fundamentally challenging: actions (variable updates) are not always fully observable. The researchers frame this as tracking a probabilistic finite-state automaton with deterministic state reveals. In this harder setting, they discover that linear RNNs can underperform non-linear variants—suggesting the limits of linear approaches when information is incomplete.

The research was submitted in February 2026 and revised through June 2026.