On the "Induction Bias" in Sequence Models

Despite the remarkable practical success of transformer-based language models, recent work has raised concerns about their ability to perform state tracking. In particular, a growing body of literature has shown this limitation primarily through failures in out-of-distribution (OOD) generalization, such as length extrapolation. In this work, we shift attention to the in-distribution implications of these limitations. We conduct a large-scale experimental study of the data efficiency of transformers and recurrent neural networks (RNNs) across multiple supervision regimes. We find that the amount of training data required by transformers grows much more rapidly with state-space size and sequence length than for RNNs. Furthermore, we analyze the extent to which learned state-tracking mechanisms are shared across different sequence lengths. We show that transformers exhibit negligible or even detrimental weight sharing across lengths, indicating that they learn length-specific solutions in isolation. In contrast, recurrent models exhibit effective amortized learning by sharing weights across lengths, allowing data from one sequence length to improve performance on others. Together, these results demonstrate that state tracking remains a fundamental challenge for transformers, even when training and evaluation distributions match.

Today's most powerful AI systems, the transformers behind modern chatbots, can struggle with a basic skill: keeping track of a state that changes step by step, like tracking the chessboard while observing piece moves in a chess game. Earlier research showed that these models often stumble when given sequences longer than the ones they were trained on. One argument is that this may not matter if we simply train them on examples of every length they will encounter. But how much data does that actually take? We ran over 200,000 experiments comparing transformers with recurrent neural networks, a classic neural network architecture that was widely used before transformers and reads input one step at a time. On simple, tightly controlled tracking tasks, transformers needed vastly more training data as the task grew longer or harder. The reason is revealing: recurrent networks naturally learn one update rule and reuse it at every step, like a proof by induction, so practice on short examples can help with longer ones. Transformers instead tend to learn separate solutions for different numbers of updates, so what they learn at one length carries over poorly to others. Step-by-step tracking therefore remains a persistent weakness of transformers, one that may help explain why they falter on very long inputs and why future AI systems may need to revisit ideas from recurrent models.