Search papers, labs, and topics across Lattice.
The paper investigates state-tracking abilities of sequence models by converting permutation composition tasks into code via REPL traces, enabling a next-token prediction training setup. They demonstrate that linear RNNs, previously shown to excel at state-tracking, also perform well in this code-based environment, outperforming Transformers. Further analysis reveals that the difficulty of state-tracking in code arises from partially observable actions, modeled as tracking the state of a probabilistic finite-state automaton, where linear RNNs can underperform non-linear RNNs.
Linear RNNs beat Transformers at state-tracking when the task is framed as code execution, but surprisingly falter when actions are only partially observable.
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.
