arXiv:2602.07599v2 Announce Type: replace
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 \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 \emph{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 \emph{Random Rational Features} act as a
universal basis for sequential dependencies, justifying our
initialization strategy, while establishing that the
\emph{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.