Rational Transductors

Mehryar Mohri

Standard Transformers dominate natural language processing, yet they possess a well-documented blind spot: they struggle with rigid sequential logic and precise state tracking. Theoretical analyses reveal that self-attention is restricted to low-complexity classes (specifically $\mathsf{AC}^0$ under hard attention or $\mathsf{TC}^0$ under soft attention). Consequently, Transformers fundamentally cannot represent certain algorithmic patterns—such as Parity or Modular Counting—uniformly across all sequence lengths without intermediate chain-of-thought.

In practice, this limitation manifests as a failure in length generalization. A Transformer might successfully learn to count to 10 during training but completely collapse when asked to count to 100 at inference time. While Recurrent Neural Networks (RNNs) and State Space Models (SSMs) attempt to resolve this by introducing a hidden state, they often impose sequential training bottlenecks or lack the expressive semantic routing capabilities of attention.

To solve this, researchers have introduced Rational Transductors, a hybrid architecture that unifies the semantic flexibility of Transformers with the rigorous, time-invariant state tracking of formal automata. By augmenting Transformers with a linear, matrix-valued recurrence derived from Weighted Finite Automata (WFA), Rational Transductors solve complex algorithmic tasks with perfect accuracy and robust length generalization, all while maintaining the $O(\log T)$ parallel training efficiency that makes Transformers highly scalable.

The Dual-Stream Architecture

Rational Transductors utilize a dual-stream architecture designed to decouple state tracking from feature mixing. This is achieved through three core mechanisms:

  1. The Rational Feature Head: Instead of a standard nonlinear RNN, the model employs a linear recurrence ($h_t = M_{x_t} h_{t-1}$) where the transition matrices $M$ are driven directly by the input tokens. Because the update is strictly linear, it can be computed rapidly using parallel associative scans (prefix sums), achieving $O(\log T)$ time complexity.
  2. Deep Rational Injection: Rather than simply adding recurrent features to the initial input embeddings, the model injects a projected view of the WFA state into every layer of the Transformer. This ensures that precise state information is available at all depths without being diluted by repeated layer normalization.
  3. Unified Scaled Cayley Parameterization: To guarantee that the recurrence remains stable—neither exploding nor vanishing over long sequences—the authors utilize a parameterization based on the Cayley transform. This enables the model to learn "orthogonal" dynamics for infinite memory (ideal for counting) or "stochastic" dynamics for forgetting irrelevant history.

Theoretical Grounding and Key Insights

The architecture is deeply grounded in the Krohn-Rhodes Theorem, which posits that any finite automaton can be decomposed into simple groups (counters) and aperiodic monoids (logic). In this framework, the Rational Head handles the "groups," while the Transformer backbone manages the "logic." This makes the system a structurally complete realization of any regular language.

Furthermore, the model's "sidecar" design provides a distinct advantage over models that interleave recurrence directly into the backbone (like Mamba). It guarantees exact parallel training without layer-wise sequential dependencies. By injecting the linear state into the attention mechanism, the model achieves Virtual Tensorization—implicitly computing interactions over a much larger state space. This elevates the model from the $\mathsf{TC}^0$ complexity class to $\mathsf{NC}^1$, the theoretical sweet spot for parallelizable algorithmic reasoning.

Empirical Evaluation: Solving the Regular Gap

The researchers evaluated Rational Transductors on synthetic algorithmic benchmarks designed to probe the theoretical limits of sequence models, specifically focusing on length generalization. Models were trained on short sequences (e.g., $L=40$) and tested on sequences up to 25 times longer ($L=1000$).

  • Modulo-5 Counting & Long-Integer Addition: The model achieved 100% accuracy on cyclic state tracking and a "Full Adder" task requiring the generation and propagation of carry bits over 1,000 digits. In contrast, standard Transformers collapsed to random chance (20%) as soon as sequence lengths exceeded the training window.
  • Base-2 Evaluation: On a high-precision task requiring the conversion of binary strings into integer values, the model learned the exact mathematical recurrence to machine precision (MSE $\approx 5.9 \times 10^{-9}$). LSTMs and standard Transformers failed due to signal attenuation and noise.
  • Computational Efficiency: Thanks to the parallel scan, the Rational Transductor outperformed sequential RNNs in latency for sequences longer than 512 tokens, maintaining sub-linear scaling even at 32k tokens.

Limitations and Future Directions

While Rational Transductors successfully capture all Regular languages, their expressivity is bounded by the state dimension $d$. Highly complex languages may require a larger $d$, which quadratically increases the cost of matrix multiplications ($O(d^2 T)$). Furthermore, because the model lacks an unbounded stack, it cannot solve "Context-Free" problems, such as matching nested parentheses of arbitrary depth (the Dyck language).

Currently, the results are demonstrated on synthetic algorithmic tasks. The natural next step is to integrate the Rational Head into large-scale language model pre-training. By combining this rigorous logic engine with massive text corpora, future work will reveal whether these theoretical guarantees translate into superior reasoning capabilities in natural language and code generation.

Summary updated

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 $\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.
BibTeX
@inproceedings{mohri2026rational,
  author = {Mehryar Mohri},
  title = {{Rational Transductors}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=uEZpyELNuB},
}
Figure