Rational Transductors：用加权有限自动机增强 Transformer 的序列推理架构

View PDF HTML (experimental)

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.

Submission history

From: Mehryar Mohri [view email]
[v1] Sat, 7 Feb 2026 16:01:10 UTC (113 KB)
[v2] Wed, 14 Oct 2026 11:51:03 UTC (116 KB)