Rational Transductors
Abstract
Standard Transformers excel at semantic modeling but struggle with rigid sequential logic
and state tracking, fundamentally limited to AC0 complexity without intermediate chain-of-
thought. In this work, we introduce Rational Transductors, a dual-stream architecture that
augments the Transformer with a linear, 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 the expressive power
of Transformers to capture all Regular Languages and NC1-complete problems (such as Parity
and Modular Counting) while preserving O(log T) parallel training efficiency.
and state tracking, fundamentally limited to AC0 complexity without intermediate chain-of-
thought. In this work, we introduce Rational Transductors, a dual-stream architecture that
augments the Transformer with a linear, 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 the expressive power
of Transformers to capture all Regular Languages and NC1-complete problems (such as Parity
and Modular Counting) while preserving O(log T) parallel training efficiency.
