On the "Induction Bias" in Sequence Models

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

cs.LGFeb 20, 2026

On the "Induction Bias" in Sequence Models

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

Organizations: Qualcomm AI Research is an initiative of Qualcomm Technologies, Inc.

Abstract

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.

Figures & tables

Figure 1: Example of the three task formats for the addition modulo

5

task applied to the sequence

2\,1\,0\,3\,4

Figure 2: Minimal dataset size for the uniform length distribution with

m=2

(parity). RNNs favor ACoT, whereas transformers favor CoT.

Fixed

Uniform

Short-to-Long

Length

Model

Format

Modulus

Transformer

Outcome Supervision

364

–

549

–

913

–

119

–

243

–

1.1K

–

2.6K

–

1.5K

–

Table 1: Minimal number of training samples required to learn the modulo addition task. A dash (–) indicates that the task was not learned at the maximum training set size.

Figure 3:

N^{*}

for the outcome supervision format with a uniform length distribution and

m=2

(parity). In the absence of intermediate supervision, single - layer RNNs significantly outperform the 6 - layer transformer.

Figure 4: Sample complexity (log scale) for transformers trained with CoT and RNNs with ACoT on the parity task. RNNs exhibit the expected improvement in sample efficiency with increasing sequence length, while transformers fail to leverage the additional supervision.

Figure 5: Sample complexity (log scale) in the Outcome Supervision format for the uniform and short-to-long length setting, with

m=2

(parity). Recurrent models require fewer training samples under the short-to-long setting, indicating that shorter sequences provide a stronger learning signal.

Figure 6: Sample complexity comparison between training a single model jointly across all sequence lengths and the cumulative sample complexity of independently trained models for each sequence length, together with the corresponding sharing factor, for the task of addition modulo

5

. The results suggest that transformers, and to a lesser extent Mamba, learn largely isolated solutions for each sequence length.

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

			Fixed				Uniform				Short-to-Long
		Length	5	10	20	30	5	10	20	30	5	10	20	30
Model	Format	Modulus
Transformer	Outcome Supervision	2	0.00	0.00	0.01	0.00	0.01	0.00	0.00	0.00	0.00	0.00	0.00	0.00
		3	0.01	0.00	0.01	0.00	0.00	0.04	0.00	0.00	0.00	0.03	0.00	0.00
		5	0.00	0.00	0.00	0.00	0.00	0.03	0.01	0.00	0.00	0.00	0.00	0.00
		10	0.00	0.02	0.00	0.00	0.00	0.00	0.01	0.00	0.01	0.00	0.00	0.00

Appendix

Table 2: Accuracy on sequences of length

2\times

the maximum used during training, normalized such that

0

corresponds to random chance.

Figure 7: Similar to Figure 6 , but for permutation composition task (

S_{5}

). The results suggest that transformers, and to a lesser extent Mamba, learn largely isolated solutions for each sequence length.

			Fixed				Uniform				Short-to-Long
		Length	5	10	20	30	5	10	20	30	5	10	20	30
Model	Format	Modulus
LSTM Dim $=256$	Outcome Supervision	2	14	202	257	413	26	34	67	109	12	13	26	16
		3	151	620	–	–	84	122	317	686	81	180	132	178
		5	1.3K	6.7K	–	–	487	876	–	–	788	1.4K	–	–
		10	6.3K	–	–	–	3.4K	–	–	–	5.1K	–	–	–

Appendix

Table 3:

N^{*}

for LSTMs with

256

and

768

hidden dimensions. We observe similar trends across both model sizes.

Fixed

Uniform

Short-to-Long

Length

Model

Format

Modulus

Transformer

2

Layers

Outcome Supervision

–

594

–

807

–

971

–

134

–

1.5K

–

1.7K

–

Appendix

Table 4:

N^{*}

for transformers with

2

and

6

layers. We observe similar trends across both model depths.

Figure 8: Sharing-factor analysis for additional transformer variants on modular addition.

Figure 9: Sharing-factor analysis for additional transformer variants on permutation composition over

S_{5}

Transformer

Transformers are neural architectures that use attention to model relationships among sequence elements in language, vision, and scientific data.

See all 528 papers

Expressivity-Efficiency Tradeoffs for Hybrid Sequence Models
Mar 9, 2026John Cooper, Ilias Diakonikolas, Mingchen Ma +1Hybrid Transformer-State Space Model Architectures Sequence Modeling
Department of Computer Sciences, University of Wisconsin-Madison
Beyond the Training Horizon: Mechanisms and Limits of Length Generalization in Looped Transformers
Sep 27, 2026Jia Liang, Xi Jin, Liangming PanLength Generalization Recurrent Transformers
Institute for Computational and Mathematical Engineering, Stanford University · MOE Key Laboratory of Computational Linguistics, School of Computer Science, Peking University
The Topological Trouble With Transformers
Apr 18, 2026Michael C. Mozer, Shoaib Ahmed Siddiqui, Rosanne LiuTransformer FFNs Recurrent Neural Networks
Google DeepMind

Mar 9, 2026J/K move · Enter open · S save

Expressivity-Efficiency Tradeoffs for Hybrid Sequence Models

John Cooper, Ilias Diakonikolas, Mingchen Ma, Frederic Sala

Department of Computer Sciences, University of Wisconsin-Madison

Hybrid Transformer-State Space Model Architectures Sequence Modeling Transformer Expressivity

Open paper AskPDF arXiv

Hybrid sequence models--combining Transformer and state-space model layers--seek to gain the expressive versatility of attention as well as the computational efficiency of state-space model layers. Despite burgeoning interest in hybrid models, we lack a basic understanding of the settings where--and underlying mechanisms through which--they offer benefits over their constituent models. In this paper, we study this question, focusing on a broad family of core synthetic tasks. For this family of tasks, we prove the existence of fundamental limitations for non-hybrid models. Specifically, any Transformer or state-space model that solves the underlying task requires either a large number of parameters or a large working memory. On the other hand, for two prototypical tasks within this family--namely selective copying and associative recall--we construct hybrid models of small size and working memory that provably solve these tasks, thus achieving the best of both worlds. Our experimental evaluation empirically validates our theoretical findings. Importantly, going beyond the settings in our theoretical analysis, we empirically show that learned--rather than constructed--hybrids outperform non-hybrid models with up to 6x as many parameters. We additionally demonstrate that hybrid models exhibit stronger length generalization and out-of-distribution robustness than non-hybrids.

Abstract

Transformer

Explore similar work

Expressivity-Efficiency Tradeoffs for Hybrid Sequence Models

Beyond the Training Horizon: Mechanisms and Limits of Length Generalization in Looped Transformers

The Topological Trouble With Transformers