Learning State-Tracking from Code Using Linear RNNs
This addresses the gap in training language models for state-tracking tasks, which is incremental as it adapts existing methods to a new representation.
The paper tackled the problem of state-tracking tasks, such as permutation composition, by converting them into code via REPL traces to make them compatible with next-token prediction training, showing that linear RNNs excel while Transformers fail, and found that linear RNNs can be worse than non-linear RNNs in probabilistic settings with partial observability.
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.