Standard Transformers excel at semantic modeling but struggle with rigid sequential logic and state tracking. Theoretical work establishes that self-attention is limited to \AC0 (under hard attention) or \TC0 (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, \NC1-complete languages (such as the word problem of S5), and fundamental separations like Parity and Modular Counting, while preserving O(logT) 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
Figure 1: Visualizing the Rational State Update. The hidden state vector ht (right) is computed as a linear transformation of the previous state ht−1 (left). Each component ht,i aggregates the weighted paths from the previous step, illustrating the "sum of paths" definition.
Figure 2: The Rational Transductor Architecture. The Rational Head extracts state variables ht . These states are injected into the Attention Stream via layer-specific projections W(l) , augmenting the semantic hidden states zt(l) .
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 ( ⊕ ) of the underlying automata.
Figure 4: Architectural Comparison. (a) Wide Recurrence: The Rational Transductor computes a single high-dimensional state ht 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 ( Lparity )
✗ †
✓
Limited to AC0 / TC0
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.
Figure 5: State tracking mechanisms for exact regular languages. (a) The Parity WFA uses a 2-state flip mechanism to track Lparity . (b) The Modulo-3 WFA generalizes this to a cyclic group structure to solve Lk for k=3 . Input ‘0‘ acts as the Identity I (self-loop), while input ‘1‘ acts as a permutation.
Figure 6: Virtual Tensorization. By injecting the linear rational state ht into the Attention mechanism, the dot product QKT implicitly computes quadratic terms of the form ht⊤Mht′ . This effectively simulates a kernel over the tensor product space ht⊗ht′ , enabling the model to capture higher-order dependencies without explicitly materializing the O(d2) 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 ( ≈20% ) on longer sequences. The Rational Transductor (blue) generalizes almost perfectly, maintaining 99% accuracy even at 25× 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(T2) ), 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=32k .
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% at 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≈8.4×10−2 ), collapsing to the random-guessing baseline. The Rational Transductor learns the exact affine recurrence, achieving near-perfect precision ( MSE≈5.9×10−9 ).
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.
Andy Yang, Blerta Veseli, Corentin Barloy +5
University of Notre Dame · 2Saarland University · 3Ruhr University Bochum +4
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.
M. Reza Ebrahimi, Michaël Defferrard, Sunny Panchal +1
Qualcomm AI Research is an initiative of Qualcomm Technologies, Inc.
Transformer-based language models exhibit an astonishing capacity to generalize to longer and more difficult problem instances than those seen in training. However, theoretical understanding of this phenomenon still lags behind. Unlike most machine learning models, the generalisation abilities of transformers inherently require considering two axes. On one hand, one must examine in-distribution statistical generalisation, which concerns the ability of a model to broaden a function from training samples to novel samples of the same distribution. On the other hand, given the sequential nature of language data, one must also consider length generalisation, which reflects whether a model trained on inputs of a given length can extrapolate to longer ones. These two notions have mostly been studied separately, leaving open how they interact. In this work, we give a joint treatment of both axes for fixed-precision transformers. We give generalisation guarantees in terms of the parameter sizes of the involved models, as well as the quantization space and the alphabet size that supply the sequences. Finally, we illustrate how the requirements in the sample count and training length trade off. In particular, we find that increasing training length can be exponentially more efficient than increasing the sample size. Experiments support predictions of the theory.
Marius Henry, Michael Rizvi-Martel, Michael Hahn
LaCoCo, Saarland University, Saarland Informatics Campus · Zuse School ELIZA · Mila & Université de Montréal