💬 NLP

On the "Induction Bias" in Sequence Models

This paper demonstrates that, unlike recurrent neural networks which effectively share state-tracking mechanisms across sequence lengths, transformers require significantly more training data as state-space and length increase and fail to generalize across lengths due to a lack of weight sharing, revealing fundamental in-distribution limitations in their state-tracking capabilities.

Original authors: M. Reza Ebrahimi, Michaël Defferrard, Sunny Panchal, Roland Memisevic

Published 2026-06-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: M. Reza Ebrahimi, Michaël Defferrard, Sunny Panchal, Roland Memisevic

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

The Big Picture: Two Different Ways of Thinking

Imagine you are teaching two different students how to solve a long math problem: adding up a very long list of numbers.

Student A (The Recurrent Model/RNN): This student is like a person walking down a hallway. They pick up a number, add it to their mental total, walk to the next room, pick up the next number, add it to the current total, and so on. They can't go back to the beginning; they only carry the "current total" in their head.
Student B (The Transformer): This student is like a person standing in a giant room with a massive whiteboard. They can see every number on the board at once. To solve the problem, they can look at the first number, then the last number, then the middle one, all at the same time, and try to figure out the answer by looking at the whole picture.

The paper asks: Which student learns this task faster, and do they learn a general rule or just memorize specific answers?

The Core Discovery: The "Induction Bias"

The authors introduce a concept called "Induction Bias." Think of this as a student's natural "learning style" or "habit."

Student A (RNN) has a strong Induction Bias: Because they must update their total step-by-step, they naturally learn a reusable rule: "To get the new total, take the old total and add the new number." This rule works for a list of 5 numbers, 50 numbers, or 500 numbers. They learn the mechanism of addition.
Student B (Transformer) lacks this bias: Because they can see the whole board, they don't need to learn the step-by-step rule. Instead, they often try to memorize the specific pattern for the length of the list they are looking at.

The Experiments: What Happened?

The researchers tested these students on synthetic tasks (like modular addition and shuffling items) to see how much practice data they needed to get good at the job.

1. The "Data Hunger" Problem

The Finding: When the list of numbers gets longer, Student A (RNN) needs only a tiny bit more practice. Student B (Transformer) needs a massive amount more practice.
The Analogy: If Student A learns to add a 5-item list, they can easily handle a 10-item list because they just keep doing the same step. Student B, however, seems to treat a 5-item list and a 10-item list as completely different subjects. To learn the 10-item list, they have to re-learn almost everything from scratch, requiring millions more examples.

2. The "Supervision" Style (How they are taught)

The researchers tried teaching them in three ways:

Outcome Only: "Here is the list. Tell me the final sum." (No hints).
Chain of Thought (CoT): "Here is the list. Write down the running total after every number, then give me the final sum."
Aligned CoT: "Here is the list. For each number, tell me the running total right next to it."

The Results:

Student A (RNN): Loved the "Aligned CoT" method. Because the teacher gave them the running total right next to the number, it perfectly matched their step-by-step walking style. They learned incredibly fast.
Student B (Transformer): Hated "Aligned CoT." It forced them to stop and write down a total for every single number, which felt unnatural for their "look at everything at once" style. They actually learned better with the "Chain of Thought" method, where they could write the whole sequence of totals at the end, allowing them to use their "whiteboard" to look back at their own previous answers.

3. The "Specialization" Trap

This is the most critical finding. The researchers asked: Do these students learn a general rule, or do they just memorize specific lengths?

Student A (RNN): They learned a general rule. If you train them on lists of length 5, 10, and 20 all mixed together, they get better at all of them. The data for the short lists helps them solve the long lists. They share their "brain power" across all lengths.
Student B (Transformer): They learned length-specific tricks. If you train them on lists of length 5, 10, and 20 mixed together, they actually get worse or stay the same. It's as if they are trying to learn three different languages at once and getting confused. They don't share their knowledge; they build a separate, isolated "circuit" for each list length.
- The "Destructive Interference": In some cases, trying to learn multiple lengths at once actually hurt the Transformer. It was more efficient to train three separate Transformers (one for length 5, one for 10, one for 20) than one big Transformer trying to do all three.

Why Does This Matter?

The paper argues that State Tracking (keeping track of a changing situation over time) is a fundamental weakness for Transformers, even when the test data looks exactly like the training data.

The "Context Rot": Because Transformers don't naturally learn the step-by-step rule, they struggle as the context (the length of the conversation or story) gets longer. They need exponentially more data to handle longer stories.
The "Agentic" Problem: The authors suggest that if we want AI agents (like robots or software assistants) to interact with the world over time, Transformers might be very inefficient because they can't easily "amortize" (spread out) their learning across different time spans.

Summary in One Sentence

While Transformers are amazing at looking at a whole picture at once, they are terrible at learning the simple, step-by-step rules needed to track changes over time, forcing them to memorize specific scenarios rather than learning a general skill, which makes them incredibly data-hungry compared to older, step-by-step models.

Technical Summary: On the "Induction Bias" in Sequence Models

Problem Statement

While transformer-based language models have achieved remarkable practical success, recent literature has highlighted their fundamental limitations in state tracking, particularly regarding out-of-distribution (OOD) generalization such as length extrapolation. However, the extent to which these limitations manifest in-distribution—specifically regarding data efficiency and the ability to generalize across different sequence lengths within the training distribution—remains less understood.

This work posits that the core issue lies in the inductive bias of the architectures. Transformers compute outputs by attending to all previous inputs and outputs within a context window, theoretically allowing for global recalculation of state. In contrast, recurrent neural networks (RNNs) must encode all relevant past information into a single hidden state vector at each time step. The authors argue that this constraint in RNNs encourages a "step-by-step" state update mechanism (analogous to the induction step in mathematical proofs), which they term "induction bias." This bias facilitates the sharing of solution mechanisms across varying sequence lengths, whereas transformers may learn length-specific solutions in isolation.

Methodology

The authors conduct a large-scale, systematic empirical study to quantify the data efficiency of transformers versus recurrent models on synthetic state-tracking tasks.

Tasks

The study formalizes state tracking as maintaining a latent state under a sequence of updates within a group-theoretic framework. Two canonical tasks are used:

Modular Addition: A commutative operation over the cyclic group $\mathbb{Z}_m$ .
Permutation Composition: A non-commutative operation over the symmetric group $S_5$ .

These synthetic tasks allow for the independent control of sequence length ( $n$ ) and state-space size (modulus $m$ ), isolating state-tracking computation from language understanding or memorization artifacts.

Supervision Regimes

Three task formats are evaluated to vary the density of the supervision signal:

Outcome Supervision: The model predicts only the final sum/state.
Chain-of-Thought (CoT): The model generates a sequence of intermediate partial sums autoregressively.
Aligned Chain-of-Thought (ACoT): The model outputs the partial sum corresponding to each input token (per-token supervision).

Models

The study compares:

Transformers: Multi-layer decoder-only architectures (GPT-2 style, 6 layers).
Recurrent Models: Long Short-Term Memory (LSTM) and Dense State-Space Models (Dense-SSMs), which utilize input-dependent, dense transition matrices.
Selective SSMs: Mamba is included for weight-sharing analysis.

Metrics

The primary metric is sample efficiency, defined as the minimal dataset size ( $N^*$ ) required for a model to achieve a validation loss below a convergence threshold. Additionally, the authors introduce a Sharing Factor ( $\kappa$ ) to quantify cross-length mechanism sharing:
$\kappa = \frac{\sum_{n=2}^{L} N^*_n}{N^*_{joint}}$
Where $N^*_n$ is the samples needed for a fixed length $n$ , and $N^*_{joint}$ is the samples needed to learn all lengths simultaneously.

$\kappa > 1$ : Indicates amortized learning (shared mechanisms).
$\kappa \approx 1$ : Indicates isolated, length-specific learning.
$\kappa < 1$ : Indicates destructive interference.

Key Results

1. Divergent Preferences for Supervision

Transformers perform most efficiently with Chain-of-Thought (CoT) supervision. They struggle significantly with Aligned CoT and Outcome Supervision, often failing to converge on non-trivial configurations.
Recurrent Models (LSTM/Dense-SSM) exhibit superior sample efficiency with Aligned CoT (ACoT) and Outcome Supervision. They struggle with CoT, likely due to a "recall bottleneck" where they must unroll intermediate computations after processing the full input.

2. Data Efficiency and Sequence Length

Transformers: The amount of training data required grows rapidly with sequence length and state-space size. Crucially, transformers fail to leverage the additional supervision signals provided by longer sequences in CoT formats; sample complexity does not decrease as expected with longer sequences.
Recurrent Models: In the ACoT regime, recurrent models show improved data efficiency as maximum sequence length increases, suggesting they effectively utilize the increased density of supervision signals. In the Outcome Supervision regime, shorter sequences provide a stronger learning signal for RNNs than longer ones.

3. Weight Sharing and Induction Bias

Transformers exhibit a low sharing factor ( $\kappa \approx 1$ or $\kappa < 1$ ) across all task formats. This indicates they learn length-specific solutions in isolation. In the CoT regime, transformers show destructive interference ( $\kappa \ll 1$ ), where training on mixed lengths is less efficient than training separate models for each length.
Recurrent Models exhibit high sharing factors ( $\kappa \gg 1$ ) in their preferred regimes (Outcome and ACoT). This confirms they internalize a reusable transition operator, allowing data from one sequence length to amortize learning costs for others.
Correlation with OOD: The paper finds a strong correlation between a high sharing factor and the ability to generalize to unseen sequence lengths (OOD). Models with low sharing factors fail to extrapolate.

Significance and Claims

The authors claim that state tracking remains a fundamental challenge for transformers even when training and evaluation distributions match. The study demonstrates that:

Transformers require extraordinarily large amounts of training data to generalize on simple state-tracking tasks, even in-distribution.
The lack of "induction bias" in transformers prevents effective weight sharing across sequence lengths, leading to isolated learning of length-specific heuristics.
The data efficiency of transformers scales poorly with sequence length, which may help explain challenges like "context rot" in large context windows.
While transformers can learn these tasks with specific supervision (CoT), they do so by learning distinct mechanisms for each length rather than a generalizable algorithm.

The paper concludes that these findings suggest end-to-end learning in "agentic" scenarios (e.g., robotics, GUI control) involving long-horizon state tracking may be significantly more challenging for transformers than previously assumed, as they lack the inherent inductive bias to efficiently share state-update mechanisms across varying temporal scales.

Limitations

The authors acknowledge that their study is limited to a representative set of synthetic tasks and models. While these tasks isolate state tracking, they do not capture all complexities of real-world sequential prediction. Furthermore, the extensive search space required for the experiments limits the number of architectures and task families that could be directly evaluated. The transfer of these data-efficiency patterns to realistic domains (code execution, embodied control) remains a direction for future work.