Rational Transductors

Standard Transformers excel at semantic modeling but struggle with rigid sequential logic and state tracking. Theoretical work establishes that self-attention is limited to $\mathsf{AC}^0$ (under hard attention) or $\mathsf{TC}^0$ (under soft attention), complexity classes that often fail to support robust length generalization on sequential problems without intermediate chain-of-thought (see hahn2020theoretical and merrill2022saturated). In this work, we introduce \emph{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 Transformers to capture all Regular Languages, $\mathsf{NC}^1$-complete problems (such as Boolean Formula Evaluation), and fundamental separations like Parity and Modular Counting, while preserving $O(\log T)$ parallel training efficiency. 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.

Modern AI language models (Transformers) are powerful at understanding meaning but surprisingly poor at following rigid rules like counting, tracking state, or doing arithmetic over long sequences. We introduce Rational Transductors, which equip Transformers with a lightweight mathematical co-processor grounded in the theory of Weighted Finite Automata and Rational Power Series. We prove that this architecture captures the full algebraic hierarchy of regular languages while preserving efficient parallel training. Our models generalize perfectly to sequences 25 times longer than those seen in training, where standard Transformers fail completely.