PaperlayerView exact revision on arXiv

Source-linked AI summary

On the "Induction Bias" in Sequence Models

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

arXiv:2602.18333v2cs.LGcs.CL

TL;DR

The paper examines how transformers and recurrent models differ in in-distribution state tracking as sequence length and state-space size vary. Through systematic experiments, it finds that transformers need more data, generalize poorly across lengths, and share parameters less effectively than recurrent models.

  • Problem

    Existing evidence emphasizes OOD state-tracking failures, leaving in-distribution data requirements and cross-length mechanism sharing difficult to quantify.

  • Method

    The paper systematically evaluates representative transformers and recurrent models on state-tracking tasks while independently varying sequence length and state-space size.

  • Results

    Transformers require significantly more data to generalize across sequence lengths, perform differently across supervision regimes, and share parameters less effectively than recurrent networks.

  • Takeaways & Limitations

    State tracking remains a substantial in-distribution challenge for transformers, which require extraordinarily large training datasets and sometimes Chain-of-Thought supervision.

  • Takeaways & Limitations

    The study uses a limited set of representative models and synthetic tasks that do not capture all complexity in real-world sequential prediction.

Abstract

from arXiv · show

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.

1. Introduction

This study examines transformers’ state-tracking limitations in-distribution, focusing on data efficiency and whether learned mechanisms transfer across sequence lengths. It argues that an induction bias—step-by-step state updates with reusable computations—explains why recurrent models share knowledge across lengths more effectively than transformers.

  • Study design: The study systematically varies sequence length and state-space size to measure in-distribution generalization error for representative transformer and recurrent models.The experiments use simple state-tracking tasks and compare multiple supervision regimes.
  • Induction bias: An induction bias decomposes multi-step dependencies into repeatable single-step state updates, enabling weight sharing across different sequence lengths.Formally, the next token depends on the current hidden state rather than the full preceding sequence.
  • Interpretation: The presence or strength of the induction bias provides a simple explanation for the study’s empirical findings, including models’ ability to transfer knowledge across lengths.Cross-length knowledge transfer is highly correlated with length generalization in the in-distribution setting.
  • Key findings: Transformers learn state-tracking tasks relatively efficiently at one fixed sequence length, but require significantly more training data to generalize in-distribution across multiple lengths.The study finds a distinct difference between the supervision regimes in which transformers and recurrent networks perform well.
  • Key findings: Unlike recurrent networks, transformers tend to fail at sharing parameters across sequence lengths and instead learn separate solution mechanisms for different lengths.The results characterize this as negligible or absent cross-length knowledge transfer in transformers compared with recurrent models.

2. Methodology

The methodology models state tracking as cumulative composition of sequential updates and evaluates models on synthetic modular-addition and permutation-composition tasks. It varies sequence-length distributions and supervision formats, defines in-distribution sample efficiency through a reliability threshold, and compares transformers with recurrent alternatives.

  • State-tracking formulation: State tracking is formalized as computing the cumulative product g1 ◦g2 ◦· · · ◦gT in a group from sequential updates.This abstracts state updates such as chess moves, variable assignments, and entity swaps.
  • Synthetic tasks: Experiments use modular addition over Zm as a commutative task and permutation composition over S5 as a non-commutative counterpart.For m = 2, modular addition reduces to binary parity.
  • Data generation: Synthetic group tasks isolate state-tracking computation while independently controlling state-space size and sequence length without language, artifact, or memorization confounds.Sequence lengths range from 2 to L, with fixed, uniform, or short-to-long sampling strategies and unique samples drawn without replacement.
  • Supervision formats: The study compares outcome supervision with process-supervised Chain-of-Thought and aligned Chain-of-Thought formats that expose intermediate partial sums.ACoT provides per-token supervision aligned with each input token, whereas outcome supervision predicts only the final sum.
  • Evaluation and models: Sample efficiency is measured by the minimal training-set size N ∗ at which at least one hyperparameter configuration reliably meets the convergence criterion.N ∗ is estimated with binary or hybrid binary–geometric search; configurations span 3 learning rates and 5 random seeds, totaling 15 per sample size.

3. In-Distribution Data Efficiency

In-distribution data efficiency depends strongly on model architecture, supervision format, and sequence-length distribution. Transformers favor CoT but fail to exploit longer sequences, whereas recurrent models benefit from ACoT and can outperform transformers under outcome supervision.

  • Supervision formats: At m = 5 and L = 20, CoT requires 1.7K samples versus 2M for Aligned CoT, showing transformers strongly prefer CoT.Aligned CoT increases sample complexity by an order of magnitude in this setting.
  • Supervision formats: Recurrent models achieve superior sample efficiency with ACoT, while transformers benefit from autoregressive intermediate outputs that enable re-attention to prior computations.ACoT aligns supervision with hidden-state evolution, whereas transformers’ CoT advantage is consistent with simulating greater computational depth.
  • Outcome supervision: Under outcome supervision, recurrent models learn higher moduli and longer sequences with orders of magnitude fewer samples, while transformers fail to converge beyond trivial configurations.Outcome supervision requires inferring latent structure and marginalizing over unobserved computational paths.
  • Sequence-length distributions: With intermediate supervision, longer sequences improve recurrent-model data efficiency but not transformers, because recurrent models exploit the additional supervised tokens.In uniform training, recurrent ACoT models require fewer data points as maximum sequence length L increases.
  • Sequence-length distributions: For recurrent models, fixed-length training is most data-efficient with ACoT, whereas short-to-long training is most effective under outcome supervision.Under ACoT, efficiency ranks fixed length, uniform, then short-to-long; under outcome supervision, shorter sequences provide a stronger learning signal.

4. Weight Sharing Across Sequence Length

Cross-length sample efficiency reveals whether sequence models learn shared state-tracking mechanisms or isolated, length-specific solutions. Transformers show weak or destructive sharing, whereas recurrent models generally amortize learning across lengths, and sharing correlates with length generalization.

  • 4. Weight Sharing Across Sequence Length: Transformers exhibit low cross-length sharing across all task formats, with κ ≈1 or κ < 1; CoT reaches κ = 0.28.These results indicate length-specific solutions, with especially extreme isolation under Chain-of-Thought supervision.
  • 4. Weight Sharing Across Sequence Length: κ ≪1 for transformers and Mamba under CoT indicates destructive interference, making mixed-length training less data-efficient than independently training each length.Length-specific solutions compete for model capacity when training spans diverse sequence lengths.
  • 4. Weight Sharing Across Sequence Length: Recurrent models show κ ≫1 under Outcome Supervision and ACoT, but sharing largely disappears under CoT at κ ≈1 without destructive interference.The reduced CoT sharing is attributed to a previously discussed recall bottleneck.
  • 4. Weight Sharing Across Sequence Length: Dense-SSM sample requirements decrease as maximum length L increases under ACoT, indicating cross-length sharing that exploits denser supervision in longer sequences.Longer sequences provide more supervision signals that can improve learning across lengths.
  • 4. Weight Sharing Across Sequence Length: High sharing factors κ ≫1 correlate with length-generalizable solutions, whereas κ ≤1 corresponds to failure to extrapolate beyond training lengths.The correlation links in-distribution data efficiency and circuit sharing to length generalization in state tracking.

5. Conclusions

The study concludes that state tracking is a severe challenge for transformers both in- and out-of-distribution, while noting that its synthetic-task evaluation covers only a limited set of models and tasks.

  • Conclusions: Transformers require extraordinarily large amounts of training data to generalize on simple state-tracking tasks.The conclusion frames this as an in-distribution limitation, not only an out-of-distribution one.
  • Conclusions: Chain-of-Thought supervision is required for transformers to learn in-distribution on even moderate sequence lengths.The conclusion suggests that end-to-end learning in applied agentic scenarios, such as robotics or GUI control, could be even more challenging.
  • Limitations: The study evaluates a limited, albeit representative, set of models and synthetic tasks that isolate state tracking.The synthetic tasks enable precise control over state-space size and sequence length but do not capture all complexity in real-world sequential prediction.
  • Limitations: Over 200,000 individual training runs were already required for the current set of models and tasks, limiting the number of architectures studied.The large parameter search space contributes to this computational constraint.

A. Implementation Details · A.1. Search Procedure for Determining N ∗

The study determines the minimal successful sample size N ∗ with a hybrid Binary-Geometric search over candidate sample sizes. Evaluations use a fixed hyperparameter grid and validation-loss threshold, with specified search limits, training settings, and distribution-dependent sample caps.

  • A.1. Search Procedure for Determining N ∗: A.1. Search Procedure for Determining N ∗: The algorithm combines an initial exponential reduction phase with a subsequent binary search phase to identify minimal sample size N ∗.The search begins from a predefined maximum sample size Nmax.
  • A.1. Search Procedure for Determining N ∗: A.1. Search Procedure for Determining N ∗: Each candidate sample size is evaluated across 15 model instances from 3 learning rates and 5 random seeds.A candidate succeeds when at least one configuration achieves validation loss below threshold ϵ.
  • A.1. Search Procedure for Determining N ∗: A.1. Search Procedure for Determining N ∗: The search uses geometric multiplier M = 1000, maximum S = 20 search steps, and success threshold ϵ = 10−4.These values define the search inputs and stopping conditions.
  • A.1. Search Procedure for Determining N ∗: A.1. Search Procedure for Determining N ∗: Successful candidates update N ∗ and trigger geometric decay or binary refinement, while failed candidates update the lower bound for binary search.If N = Nmax fails, the procedure returns −1.
  • A.1. Search Procedure for Determining N ∗: A.1. Search Procedure for Determining N ∗: The hyperparameter grid varies learning rate across {10−3, 10−4, 10−5} and seeds across {10, 20, 30, 40, 50}.The Cartesian product yields 15 configurations per evaluation.
  • A.1. Search Procedure for Determining N ∗: A.1. Search Procedure for Determining N ∗: Models train for at most 250k optimization steps with batch size 64 using Adam, independently of N, with early stopping on the validation-loss criterion.The stated training budget applies regardless of training-set size.
  • A.1. Search Procedure for Determining N ∗: A.1. Search Procedure for Determining N ∗: The maximum training set size is capped at the minimum of 16M feasible samples and the total sequences available under the specified maximum sequence length L and modulus m.The final training set size is obtained after deducting the validation set; available-sequence counts depend on the distribution.

A.2. Evaluation · A.3. Models

The evaluation protocol uses strictly disjoint training and validation sets with fixed validation samples across training-set sizes. The models include GPT-2-based transformers, Mamba, LSTM, Dense-SSM, and smaller transformer/LSTM variants with specified dimensions and architectures.

  • A.2. Evaluation: Training and validation sets are strictly disjoint throughout the evaluation.The validation set remains separate from training data at every sequence length.
  • A.2. Evaluation: The validation set contains 2,000 samples or at most 20% of available data.The same validation set is retained across training-set sizes, except for random-seed variations.
  • A.2. Evaluation: At each sequence length, at most 20% of available samples are used for validation, with the remainder reserved for training.Multi-digit integers are represented as single tokens for all tasks.
  • A.3. Models: The transformer follows GPT-2 with 6 layers and model dimension 256.Its MLP expansion factor is 4, while other architectural parameters follow GPT-2 small defaults.
  • A.3. Models: The Mamba model has 6 layers, model dimension 256, expansion factor 2, state size 64, and convolution kernel size 4.Expansion factor 2 corresponds to inner dimension 512.
  • A.3. Models: LSTM and Dense-SSM use a single-layer recurrent cell followed by a linear classification head.The LSTM uses input and hidden dimension 768, whereas Dense-SSM uses dimension 256.
  • A.3. Models: Additional experiments use a 2-layer transformer and a single-layer LSTM with hidden dimensionality 256.Sample-efficiency results for these variants are provided in the paper’s appendix.

B. Additional Experimental Results · B.1. Evaluating Length Generalization

This subsection evaluates length generalization by measuring normalized accuracy on sequences twice as long as those seen during training. Models are compared using the maximum available training set size for each configuration.

  • B.1. Evaluating Length Generalization: Accuracy is normalized so that 0 corresponds to random chance.The normalization makes scores interpretable relative to chance performance.
  • B.1. Evaluating Length Generalization: All models are trained with the maximum available training set size for each configuration.Thus, the reported comparison uses the largest available training set in each configuration.
  • B.1. Evaluating Length Generalization: The evaluation uses sequences of length 2× the maximum length used during training.This directly tests performance beyond the training length.

B.2. Permutation Composition Task

The permutation composition task extends state-tracking evaluation to the non-commutative symmetric group S_m, whose elements are mapped to integer tokens. Results reproduce earlier patterns, with transformers and, to a lesser extent, Mamba learning largely isolated solutions for each sequence length.

  • B.2. Permutation Composition Task: The task uses permutations from the symmetric group S_m, with cardinality |S_m| = m!, bijectively mapped to integer tokens.Each permutation π ∈ S_m is mapped to a unique token in {0, 1, . . . , m! −1}.
  • B.2. Permutation Composition Task: Permutation composition raises state-tracking complexity because the model cannot rely on the order-invariance property of abelian groups.The composition operator is non-commutative in this task.
  • B.2. Permutation Composition Task: The symmetric group S_m provides a canonical non-commutative structure for evaluating whether models internalize finite-group transition dynamics.Cayley’s Theorem motivates this choice by relating every finite group to a subgroup of a symmetric group.
  • B.2. Permutation Composition Task: The experiments observe the same patterns as Section 4 and Figure 6, supporting generalization of the findings to non-commutative state-tracking tasks.These observations are reported for the permutation composition task.
  • B.2. Permutation Composition Task: Transformers, and to a lesser extent Mamba, learn largely isolated solutions for each sequence length.Figure 7 presents this result for the permutation composition task on S5.

B.3. Data Efficiency Evaluation for Smaller Models

The evaluation compares data efficiency across smaller LSTMs and transformers, finding similar trends across hidden dimensions and model depths.

  • B.3. Data Efficiency Evaluation for Smaller Models: Table 3 evaluates N ∗ for LSTMs with 256 and 768 hidden dimensions.The reported trends are similar across both model sizes.
  • B.3. Data Efficiency Evaluation for Smaller Models: Table 4 evaluates N ∗ for transformers with 2 and 6 layers.The reported trends are similar across both model depths.

B.4. Weight Sharing in Additional Transformer Variants

This section tests whether the observed cross-length sharing behavior is specific to the GPT-2-style transformer by evaluating Llama 3- and Pythia-based variants on modular addition and permutation composition over S5.

  • Additional Transformer Variants: The study evaluates Llama 3 and Pythia transformer variants to test whether cross-length sharing behavior generalizes beyond the GPT-2-style model.The variants match the main transformer in depth, hidden size, attention heads, vocabulary size, and effective MLP intermediate size.
  • Additional Transformer Variants: Sharing-factor analysis covers modular addition and permutation composition over S5 for the additional transformer variants.
Loading 2602.18333v2…