Rational Transductors

📄 arXiv: 2602.07599v1 📥 PDF

作者: Mehryar Mohri

分类: cs.LG

发布日期: 2026-02-07

💡 一句话要点

提出Rational Transductors，解决Transformer在序列逻辑和状态追踪上的泛化难题。

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: Transformer 加权有限自动机 序列建模 长度泛化 理性注入

📋 核心要点

  1. Transformer在序列逻辑和状态追踪上存在泛化性问题，无法有效处理需要精确状态转移的任务。
  2. Rational Transductors通过引入基于加权有限自动机的矩阵值递归，增强了Transformer处理序列逻辑的能力。
  3. 实验表明，Rational Transductors在算法任务上实现了更好的长度泛化，解决了Transformer的正则差距。

📝 摘要（中文）

标准的Transformer在语义建模方面表现出色，但在严格的序列逻辑和状态追踪方面存在困难。理论研究表明，自注意力机制的能力受到限制，在没有中间的思维链的情况下，通常难以在序列问题上实现鲁棒的长度泛化。本文提出了Rational Transductors，一种双流架构，通过源自加权有限自动机（WFA）的矩阵值递归来增强Transformer。通过一种深度理性注入方案，将理性状态信息注入到注意力机制中，我们的框架严格地将Transformer的表达能力推广到捕获所有正则语言、NC1完全问题（如布尔公式评估）以及奇偶性和模计数等基本分离，同时保持O(L + log T)的并行时间复杂度。我们通过严格的学习理论来支持该架构：我们证明了随机理性特征充当序列依赖关系的通用基础，证明了我们的初始化策略的合理性，同时确定了可微理性特征机制对于缩小表示紧凑性差距是必要的。理论分析和实验结果表明，Rational Transductors解决了“正则差距”，从而在标准Transformer失败的算法任务上实现了鲁棒的长度泛化，而没有传统RNN的顺序计算瓶颈。

🔬 方法详解

问题定义：Transformer在处理需要精确状态转移和序列逻辑的任务时，存在泛化性问题。例如，对于正则语言的识别，Transformer的自注意力机制在理论上存在表达能力限制，难以实现鲁棒的长度泛化。现有方法，如RNN，虽然擅长处理序列问题，但存在顺序计算的瓶颈，难以并行化。

核心思路：Rational Transductors的核心思路是通过引入源自加权有限自动机（WFA）的矩阵值递归，为Transformer注入理性状态信息。WFA能够精确地表示正则语言，通过将其融入Transformer，可以增强模型处理序列逻辑的能力。这种设计旨在弥合Transformer在语义建模和序列逻辑推理之间的差距。

技术框架：Rational Transductors采用双流架构，包括一个标准的Transformer流和一个WFA流。WFA流负责维护序列的状态信息，并通过“深度理性注入”方案将状态信息注入到Transformer的注意力机制中。Transformer流则负责进行语义建模。两个流相互作用，共同完成任务。整体架构允许并行计算，避免了传统RNN的顺序计算瓶颈。

关键创新：Rational Transductors的关键创新在于将WFA与Transformer相结合，并提出“深度理性注入”方案。这种结合使得模型既能利用Transformer的语义建模能力，又能利用WFA的序列逻辑推理能力。此外，论文还提出了随机理性特征和可微理性特征的概念，并从理论上证明了它们的有效性。

关键设计：WFA流使用矩阵值递归来表示状态转移，矩阵的维度与WFA的状态数相关。深度理性注入方案通过将WFA的状态信息与Transformer的注意力权重相结合，影响注意力机制的计算。论文还详细描述了随机理性特征的初始化策略和可微理性特征的训练方法。损失函数的设计旨在鼓励模型学习到能够有效表示序列逻辑的WFA状态。

📊 实验亮点

Rational Transductors在多个算法任务上取得了显著的性能提升，尤其是在长度泛化方面。实验结果表明，Rational Transductors能够有效地解决Transformer的正则差距，并在一些任务上超越了传统的RNN模型。具体的性能数据和对比基线在论文中详细给出。

🎯 应用场景

Rational Transductors在需要精确序列逻辑和状态追踪的领域具有广泛的应用前景，例如自然语言处理中的语法分析、程序语言处理、生物序列分析以及机器人控制等。该研究有望提升模型在算法任务和复杂逻辑推理任务上的性能，并为开发更强大的通用人工智能系统提供新的思路。

📄 摘要（原文）

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.