# Rational Transductors

arXiv: https://arxiv.org/abs/2602.07599 · HTML: https://mlsanity.com/paper/2602.07599/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 71 references that are in the map.
- First posted on arXiv 7 Feb 2026.

## Builds on (most cited first, 30 of 32)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [On Layer Normalization in the Transformer Architecture](https://mlsanity.com/paper/2002.04745/) (2020)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Generating Sequences With Recurrent Neural Networks](https://mlsanity.com/paper/1308.0850/) (2013)
- [Linear Transformers Are Secretly Fast Weight Programmers](https://mlsanity.com/paper/2102.11174/) (2021)
- [Hungry Hungry Hippos: Towards Language Modeling with State Space Models](https://mlsanity.com/paper/2212.14052/) (2022)
- [Jamba: A Hybrid Transformer-Mamba Language Model](https://mlsanity.com/paper/2403.19887/) (2024)
- [Unitary Evolution Recurrent Neural Networks](https://mlsanity.com/paper/1511.06464/) (2015)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [Kimi Linear: An Expressive, Efficient Attention Architecture](https://mlsanity.com/paper/2510.26692/) (2025)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Deep Multi-task Representation Learning: A Tensor Factorisation Approach](https://mlsanity.com/paper/1605.06391/) (2016)
- [A Logic for Expressing Log-Precision Transformers](https://mlsanity.com/paper/2210.02671/) (2022)
- [Stable Recurrent Models](https://mlsanity.com/paper/1805.10369/) (2018)
- [A Formal Framework for Understanding Length Generalization in Transformers](https://mlsanity.com/paper/2410.02140/) (2024)
- [PaTH Attention: Position Encoding via Accumulating Householder Transformations](https://mlsanity.com/paper/2505.16381/) (2025)
- [Transformers in Uniform TC0](https://mlsanity.com/paper/2409.13629/) (2024)
- [Stack Attention: Improving the Ability of Transformers to Model Hierarchical Patterns](https://mlsanity.com/paper/2310.01749/) (2023)
- [Structured Sparse Transition Matrices to Enable State Tracking in State-Space Models](https://mlsanity.com/paper/2509.22284/) (2025)

## Built on by (most cited first, 1 of 1)

- [Olmo Hybrid: From Theory to Practice and Back](https://mlsanity.com/paper/2604.03444/) (2026)

## Abstract (arXiv)

Standard Transformers excel at semantic modeling but struggle with rigid sequential logic and state tracking. Theoretical work establishes that self-attention is limited to AC0 (under hard attention) or TC0 (under soft attention), complexity classes that often fail to support robust length generalization on sequential problems without intermediate chain-of-thought citephahn2020theoretical, hao2022formal, merrill2022saturated. In this work, we introduce 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 the expressive power of Transformers to capture all Regular Languages, NC1-complete languages (such as the word problem of S5), 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 Random Rational Features act as a universal basis for sequential dependencies, justifying our initialization strategy, while establishing that the 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.