Rational Transductors
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917257135783936 |
|---|---|
| author | Mohri, Mehryar |
| author_facet | Mohri, Mehryar |
| contents | 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. 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 problems (such as Boolean
Formula Evaluation), and fundamental separations like Parity and
Modular Counting, while preserving $O(L + \log T)$ parallel time
complexity. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_07599 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Rational Transductors Mohri, Mehryar Machine Learning 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. 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 problems (such as Boolean Formula Evaluation), and fundamental separations like Parity and Modular Counting, while preserving $O(L + \log T)$ parallel time complexity. 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. |
| title | Rational Transductors |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2602.07599 |