Rational Transductors

Mehryar Mohri

cs.LGFeb 7, 2026

Rational Transductors

Authors: Mehryar Mohri

Organizations: Google Research

Abstract

Standard Transformers excel at semantic modeling but struggle with rigid sequential logic and state tracking. Theoretical work establishes that self-attention is limited to $\AC^0$ (under hard attention) or $\TC^0$ (under soft attention), complexity classes that often fail to support robust length generalization on sequential problems without intermediate chain-of-thought \citep{hahn2020theoretical, hao2022formal, merrill2022saturated}. In this work, we introduce Rational Transductors, a dual-stream architecture that augments the Transformer with a matrix-valued recurrence derived from Weighted Finite Automata (WFA). By injecting rational state information into the attention mechanism via a Deep Rational Injection scheme, our framework strictly generalizes the expressive power of Transformers to capture all Regular Languages, $\NC^1$ -complete languages (such as the word problem of $S_5$ ), and fundamental separations like Parity and Modular Counting, while preserving $O(\log T)$ parallel training efficiency. We ground the architecture in a rigorous learning theory: we prove that Random Rational Features act as a universal basis for sequential dependencies, justifying our initialization strategy, while establishing that the Differentiable Rational Feature regime is necessary to close the representational compactness gap. Theoretical analysis and empirical results demonstrate that Rational Transductors solve the ``Regular Gap,'' enabling robust length generalization on algorithmic tasks where standard Transformers fail, without the sequential computational bottlenecks of traditional RNNs.

Figures & tables

Panel of Figure 1 — Figure 1: Visualizing the Rational State Update. The hidden state vector $\mathbf{h}_{t}$ (right) is computed as a linear transformation of the previous state $\mathbf{h}_{t-1}$ (left). Each component $h_{t,i}$ aggregates the weighted paths from the previous step, illustrating the "sum of paths" definition.

Panel of Figure 2 — Figure 2: The Rational Transductor Architecture. The Rational Head extracts state variables $\mathbf{h}_{t}$ . These states are injected into the Attention Stream via layer-specific projections $\mathsf{W}^{(l)}$ , augmenting the semantic hidden states $\mathbf{z}_{t}^{(l)}$ .

Panel of Figure 3 — Figure 3: The Universal Rational Transductor. The architecture instantiates parallel heads with distinct dynamical biases: Orthogonal (top) for infinite memory and Stochastic (bottom) for discrete switching. These independent features are concatenated, corresponding to the direct sum ( $\oplus$ ) of the underlying automata.

Panel of Figure 4 — Figure 4: Architectural Comparison. (a) Wide Recurrence: The Rational Transductor computes a single high-dimensional state $h_{t}$ directly from the input via a parallel scan, injecting it into all layers. (b) Deep Recurrence: Stacked architectures (e.g., H3, Mamba) interleave recurrence, where Layer $k$ depends on the output of Layer $k-1$ , reintroducing a sequential bottleneck during training.

Task / Property	Transformer	Transductor	Theoretical Reason
Parity ( $L_{\text{parity}}$ )	✗ †	✓	Limited to $\mathsf{AC}^{0}$ / $\mathsf{TC}^{0}$
Modular Counting	✗	✓	Lack of cyclic state vs. WFA exactness
All Regular Languages	✗	✓	Star-free limitation vs. Rational completeness
Length Generalization	✗	✓	Positional drift vs. Time-invariant recurrence
All Context-Free Languages	✗	✗	Lack of unbounded memory stack

Table 1: Theoretical comparison of capabilities between finite-depth Transformers and Rational Transductors. Transductors strictly expand expressivity to include all regular languages while sharing the fundamental limitation on context-free grammars.

Panel of Figure 5 — Figure 5: State tracking mechanisms for exact regular languages. (a) The Parity WFA uses a 2-state flip mechanism to track $L_{\text{parity}}$ . (b) The Modulo-3 WFA generalizes this to a cyclic group structure to solve $L_{k}$ for $k=3$ . Input ‘0‘ acts as the Identity $\mathsf{I}$ (self-loop), while input ‘1‘ acts as a permutation.

Panel of Figure 6 — Figure 6: Virtual Tensorization. By injecting the linear rational state $h_{t}$ into the Attention mechanism, the dot product $QK^{T}$ implicitly computes quadratic terms of the form $h_{t}^{\top}Mh_{t^{\prime}}$ . This effectively simulates a kernel over the tensor product space $h_{t}\otimes h_{t^{\prime}}$ , enabling the model to capture higher-order dependencies without explicitly materializing the $O(d^{2})$ state space.

Figure 7: The Regular Gap (Modulo-5 Counting). The models are trained on short sequences (

L=50

) and evaluated on longer lengths up to

L=500

. The Standard Transformer (red) achieves high accuracy on the training distribution but fails to generalize, collapsing to near-random chance (

20\%

) as length increases. The Rational Transductor (blue), leveraging the strictly orthogonal parameterization, learns the exact underlying automaton and maintains 100% accuracy across all tested lengths. Results are averaged over 5 random seeds; standard deviations are negligible (

<0.01\%

) and omitted for clarity (see Appendix B ).

Figure 8: Length Generalization. Models were trained only on sequences of length

L=40

(vertical dashed line) and evaluated on lengths up to

L=1000

. The Standard Transformer (red) overfits to the training positions; its accuracy collapses to random chance (

\approx 20\%

) on longer sequences. The Rational Transductor (blue) generalizes almost perfectly, maintaining

99\%

accuracy even at

25\times

the training length. This validates the algebraic exactness guarantee (Theorem 6 ). Shaded regions (invisible at this scale) denote standard deviation across 5 runs.

Figure 9: Latency vs. Sequence Length. Wall-clock inference latency (ms) on a log-log scale. The Sequential RNN (red) scales linearly (

O(T)

), becoming prohibitively slow for long sequences. The Transformer (green) exhibits quadratic scaling (

O(T^{2})

), eventually running out of memory. The Rational Transductor (blue) leverages parallel associative scans to achieve sub-linear scaling, outperforming the RNN on sequences longer than

T=512

and maintaining high throughput even at

T=32\text{k}

Figure 10: Experiment D: Long-Integer Addition. Sequence-level accuracy (exact match of the entire sum). The Standard Transformer (red) fits the training distribution (

L=20

) but fails completely on longer sequences (

0\%

L=100

), unable to propagate carry bits over long distances. The Universal Rational Transductor (blue), leveraging a Stochastic head, learns the exact finite state automaton for addition. It generalizes perfectly to

L=1000

digits, demonstrating that the architecture can autonomously learn the correct switching logic for the task.

Figure 11: Quantitative Precision (Base-2 Evaluation). We trained models to compute the integer value of binary strings of length

L=64

using double precision. Standard architectures (LSTM, Transformer) fail completely (

MSE\approx 8.4\times 10^{-2}

), collapsing to the random-guessing baseline. The Rational Transductor learns the exact affine recurrence, achieving near-perfect precision (

MSE\approx 5.9\times 10^{-9}

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Model Architecture
Config / Task	Modulo Counting	Length Gen.	Long Addition	Base-2 Eval
	(Sec. 7.1)	(Sec. 7.2)	(Sec. 7.4)	(Sec. 7.5)
Hidden Dim ( $d_{\text{model}}$ )	32	32	32	12 (Rational Transductor) / 32 (Transformer)
Rational State Dim ( $d_{\text{rat}}$ )	8	8	4	12
Layers	2	2	2	1 (Rational Transductor) / 3 (Transformer)
Heads	4	4	4	4

Appendix

Table 2: Hyperparameters for Rational Transductor Experiments. (RT: Rational Transductor, TF: Transformer.)

Recurrent Transformers

Recurrent Transformers reuse layers or state across steps to extend context, reasoning depth, and sequence modeling with less parameter growth.

See all 179 papers

Algebraic Decomposition Theory for Transformer Length Generalization
Aug 13, 2026Andy Yang, Blerta Veseli, Corentin Barloy +5Transformer Length Generalization
University of Notre Dame · 2Saarland University · 3Ruhr University Bochum +4
On the "Induction Bias" in Sequence Models
Feb 20, 2026M. Reza Ebrahimi, Michaël Defferrard, Sunny Panchal +1Transformer State Tracking
Qualcomm AI Research is an initiative of Qualcomm Technologies, Inc.
Quantitative Generalization Bounds for Multi-Layer Transformers: A Few Long Strings can Beat Many Short Ones
Oct 26, 2026Marius Henry, Michael Rizvi-Martel, Michael HahnLanguage Model Generalization Generalization Bounds
LaCoCo, Saarland University, Saarland Informatics Campus · Zuse School ELIZA · Mila & Université de Montréal

Aug 13, 2026J/K move · Enter open · S save

Algebraic Decomposition Theory for Transformer Length Generalization

Andy Yang, Blerta Veseli, Corentin Barloy, Michaël Cadilhac+4

University of Notre Dame · 2Saarland University · 3Ruhr University Bochum+4

Transformer Length Generalization

Open paper AskPDF arXiv

Transformer-based language models are known to sometimes generalize to sequences longer than seen during training, but we lack a precise characterization of which tasks admit length generalization. It is not even known which regular languages transformers length-generalize on -- and this is a foundational class of languages. Our contributions are to establish the first complete characterization of which regular languages transformers length-generalize on and provide a decision algorithm running in polynomial time in the size of the language's syntactic monoid. These results rely on an effective characterization of the regular languages in C-RASP, a recently-established formalism that expresses which languages transformers length-generalize on. This characterization is challenging because classical tools like Krohn-Rhodes decomposition theory for finite semigroups are insufficient for C-RASP. Firstly, the basic building blocks of Krohn-Rhodes theory -- flip-flop and simple groups -- are not expressible in C-RASP. Secondly, the basic building block of C-RASP (unbounded counting) is not expressible by the finite semigroups of Krohn-Rhodes theory. Thus, length generalization on regular languages is controlled by an algebraic property that is invisible to classical finite decomposition theory. We generalize classical decomposition theory from finite semigroups to the infinite additive group on the integers, allowing us to characterize C-RASP in terms of iterated wreath products of the integers and derive a provable polynomial-time decision algorithm for regular language membership. Experiments across a broad test suite of regular languages confirm that our theory captures transformers' length-generalization behavior more accurately than existing classifications.

Abstract

Recurrent Transformers

Explore similar work

Algebraic Decomposition Theory for Transformer Length Generalization

On the "Induction Bias" in Sequence Models

Quantitative Generalization Bounds for Multi-Layer Transformers: A Few Long Strings can Beat Many Short Ones