An Algebraic View of the Expressivity of Recurrent Language Models¶

会议: ICML2026
arXiv: 2606.01765
代码: 无
领域: LLM/NLP
关键词: 循环语言模型、形式语言、转移幺半群、有限精度、状态空间模型

一句话总结¶

这篇论文把 RNN/SSM 的形式语言表达能力统一为一个代数问题：在固定数值语义后，模型能识别的语言由其层级转移幺半群及其 wreath product 决定，并且同一架构在浮点与无符号整数语义下会得到完全不同的计数能力。

研究背景与动机¶

领域现状：近年来，语言模型表达能力分析常把 RNN、SSM、Transformer 等架构当作形式语言识别器来研究，目标是回答它们能否实现括号匹配、模计数、有限自动机模拟等经典计算任务。这个方向的理论结果经常会转化为架构启发，例如线性 RNN 或 Mamba 类状态空间模型是否能长期保存计数信息。

现有痛点：文献中的结论并不一致。一部分工作在精确实数或有理数算术下证明 RNN 具有很强的计算能力，甚至可达图灵完备；另一部分工作在有限精度或资源受限假设下证明它们只能模拟有限自动机。问题不在于某一边“错了”，而在于这些证明默认的算术模型、舍入规则、溢出语义和求值顺序并不相同。

核心矛盾：神经网络公式看上去是连续实数运算，但真实部署一定发生在离散、有限、带舍入的数值系统上。若理论证明依赖实数域中的结合律、无限精度或可任意重排的代数恒等式，它就不一定能迁移到浮点实现；反过来，若只说“有限精度”却不规定具体运算语义，也无法得到可复验的表达能力结论。

本文目标：作者希望给出一个统一框架，把循环语言模型的表达能力拆成三个可替换部分：架构的状态转移结构、层间 wiring 的组合方式、以及底层算术语义。这样当结论发生冲突时，可以精确定位到底是架构本身不同，还是数值语义不同。

切入角度：论文从自动机理论中的幺半群出发，把每个 recurrent core 看成有限状态转移系统，把深层 RNN 的层级组合看成 transformation monoid 的 wreath product。识别一个形式语言不再是直接构造网络参数，而是判断目标语言的 syntactic monoid 是否能除尽模型可实现的幺半群结构。

核心 idea：用“固定算术语义后的转移幺半群”替代含糊的实数网络公式，从而把 RNN/SSM 表达能力归约为有限代数中的可除性问题。

方法详解¶

论文不是提出新的训练算法，而是提出一套分析循环语言模型表达能力的代数框架。整体逻辑是：先把一层 recurrent module 抽象成 algebraic core，再把多层网络抽象成 core 的 cascade；接着用 wreath product 给出所有可能的层级转移上界，再用 realized input set 收紧到真实 wiring 能触达的转移；最后把语言识别问题接到 syntactic monoid 上，得到“目标语言能否被识别”的代数判据。

整体框架¶

输入是一类循环式语言模型、一个有限输入字母表、一个固定的编码器和数值语义；输出不是模型预测，而是一个关于可识别语言族的结构化刻画。框架先为每层定义状态集合 \(Q\)、输入集合 \(X\)、输出集合 \(Y\)、状态转移 \(f:Q\times X\to Q\) 和读出 \(g:Q\times X\to Y\)。对每个输入 \(x\)，状态转移 \(f_x:Q\to Q\) 生成该层的 transition monoid。多层网络通过 wiring map 把上一层的输入/输出变成下一层输入，因此全局状态空间是各层状态的笛卡尔积。

随后，论文用 wreath product 描述层级依赖：下层状态会影响上层在当前时间步看到的输入，因此深层 RNN 不是简单的并行直积，而是一个级联转移系统。为了避免把不可达输入也算进表达能力，作者进一步定义相对于输入集合 \(T\) 的 reachable input set 和 realized transition monoid，只保留实际会被 encoder 与 wiring 激活的层内转移。

最后，作者把模型变成语言 acceptor：追加一个 accepting core，使接受条件成为最后一层状态上的集合，而不是临时读出值上的后处理。这样就能使用 Eilenberg 风格的代数语言理论：若模型识别语言 \(\mathcal{L}\)，则 \(\mathcal{L}\) 的 syntactic monoid 必须 divide 该模型的 realized wreath product。

关键设计¶

Algebraic core 与 transition monoid:
- 功能：把每个 recurrent layer 抽象成一个有限或离散状态转移器，保留“输入驱动状态变化”这一最核心的结构。
- 核心思路：对 core \(\mathfrak{c}=(Q,X,Y,f,g)\)，每个输入 \(x\in X\) 诱导一个自映射 \(f_x:Q\to Q\)，所有这些映射在函数复合下生成 \(M_{\mathfrak{c}}=\langle f_x\mid x\in X\rangle\)。读出 \(g\) 不直接进入转移幺半群，因为它只决定状态如何被观察，而不决定状态动力学。
- 设计动机：这样可以把“模型内部能保存什么动态信息”和“最终如何读出答案”分离开，避免把 decoder 的表达能力误算进 recurrent dynamics。
Realized wreath product:
- 功能：刻画多层 RNN 在给定 wiring 与输入字母表下真正可实现的全局转移结构。
- 核心思路：深层 cascade 的 ambient 上界是各层 transition monoid 的迭代 wreath product，但该上界允许上层接收任意 \(X_n\) 中的输入。作者定义 layer-input dependency map \(\varphi_n^T\)，只收集从第一层输入集合 \(T\) 出发能传到第 \(n\) 层的输入，再由这些可达输入生成 \(M_n^T\)。最终得到 \(\mathbb{W}_{\mathcal{R}}^T=(M_1^T,Q_1)\wr\cdots\wr(M_N^T,Q_N)\)。
- 设计动机：这个收紧避免了“架构形式上允许，但 wiring 永远不会触发”的虚假表达能力，同时也让改变 encoder 或输入分布时可以局部更新分析。
把算术语义纳入模型定义:
- 功能：解释同一 RNN/SSM 架构为何在不同论文中得到矛盾的表达能力结论。
- 核心思路：作者把 arithmetic model 写成 \(\mathfrak{M}=(\mathcal{D},\mathcal{O},\square)\)，其中 \(\mathcal{D}\) 是可表示值域，\(\mathcal{O}\) 是运算集合，\(\square\) 是舍入/截断映射。表达式必须配有固定 evaluation tree，并且 recurrent update 必须满足先完成时间 \(t\) 再进入 \(t+1\) 的 recurrence-consistent evaluation。
- 设计动机：浮点加法和乘法不满足结合律，编译器或硬件重排会改变结果；如果不把这些语义固定下来，所谓“能否识别某个语言”的问题本身就不是良定义的。

损失函数 / 训练策略¶

本文不涉及训练损失或优化策略。它研究的是 expressivity 而非 learnability：给定一个架构族和数值语义，是否存在某个参数化实例可以识别目标形式语言。作者也明确说明，框架不保证这些参数能通过梯度下降自动找到。

实验关键数据¶

主实验¶

本文的“主实验”是理论结果与 case study，而不是数据集 benchmark。最核心的结果是把不同算术模型下的表达能力差异放到同一张代数表中比较。

对象	判据 / 结果	结论	影响
单层 algebraic core	\(M_{\mathfrak{c}}=\langle f_x\rangle\)	层内动力学由 transition monoid 决定	可把架构能力转为幺半群问题
深层 algebraic RNN	\(M_{\mathcal{R}}^T\leq W_{\mathcal{R}}^T\)	全局转移嵌入 realized wreath product	层级组合可用 wreath product 分析
语言 acceptor	\(M(\mathcal{L})\prec M_{\mathcal{R}^+}^{e(\Sigma)}\leq W_{\mathcal{R}^+}^{e(\Sigma)}\)	目标语言的 syntactic monoid 必须 divide 模型转移结构	给出不可识别证明与可识别构造的统一入口
非负 diagonal SSM + 浮点	core monoid aperiodic	无法实现需要非平凡群的模计数	修正“同一架构可计数”的过强说法
diagonal SSM + 无符号整数量化	可包含 \(\mathbb{Z}/2^k\mathbb{Z}\)	可支持偶数模计数类结构	数值语义改变会改变表达能力

消融实验¶

下面的表相当于算术语义分析：保持 diagonal SSM 形式基本相同，只替换 recurrence multiplier 与数值模型，观察 core monoid 中可出现的群结构。

配置	关键指标	说明
非负 recurrence + 浮点 fp	只有平凡子群，core monoid 属于 aperiodic 类	非负浮点仿射更新是有限链上的保序映射，不能产生非平凡循环
允许 signed multiplier + 浮点 fp	可出现 \(\mathbb{Z}/2\mathbb{Z}\)，但子群至多是 elementary abelian 2-groups	负乘子带来反序映射，因此最多实现二阶翻转结构
非负 recurrence + 无符号整数 \(\mathrm{int}^p\)	可实现 \(\mathbb{Z}/2^k\mathbb{Z}\)，\(k\leq p\)	wraparound 加法 \(q\mapsto q+1\bmod 2^p\) 直接给出循环计数器
不固定 evaluation order	表达能力陈述不再良定义	非结合浮点运算被重排后，单步 recurrence 本身可能变成不同函数

关键发现¶

最大的贡献不是某个新定理单点，而是把“架构、wiring、算术语义”三件事拆开，使先前冲突结论可以被放到同一坐标系下比较。
对 finite-precision 模型来说，所有诱导的 transition monoid 都是有限的，因此可识别语言最多是 regular；若要讨论非正则能力，必须显式引入随长度增长的精度、深度或外部资源。
diagonal SSM 的 case study 很有启发性：同一类形式 recurrence 在非负浮点语义下不能做偶数模计数，但在无符号整数 wraparound 语义下可以构造计数器。

亮点与洞察¶

论文把“数值语义是模型的一部分”说得非常彻底。很多表达能力证明默认实数代数恒等式成立，但真实浮点系统的舍入、溢出和非结合性会改变转移函数本身，这一点在长序列 recurrence 中尤其关键。
realized wreath product 是一个很干净的抽象。它既保留深层 RNN 中“下层控制上层”的层级结构，又避免把不可达输入导致的虚假 monoid 加进来，适合做精确的不可表达性证明。
接受核心的设计把 decoder 从临时后处理变成网络 cascade 的一层，让语言识别能严格接上 syntactic monoid。这个小改动让机器学习式 RNN 与经典自动机理论之间的接口更自然。
对实际架构设计的启发是：如果某个任务依赖稳定计数或群结构，仅靠“看起来类似 recurrence”的连续公式并不够，还要检查部署数值类型是否真的支持相应的代数循环。

局限与展望¶

本文分析的是存在性表达能力，不分析参数是否能被训练出来。一个架构在代数上可表达某语言，并不意味着 SGD 会找到对应参数。
框架主要覆盖有限精度语义，因此自然落在 regular language 范围内；对随序列长度增长的精度、外部 memory 或动态深度模型，还需要扩展到无限幺半群或资源敏感版本。
论文聚焦显式 recurrent 架构，尤其是 RNN 与 diagonal SSM。Transformer 若要纳入同一框架，需要先被形式化为某种 recurrent computation，这对全注意力模型并不直接。
case study 主要重析 diagonal SSM 的已知表达能力争议，而不是系统覆盖所有现代 sequence model。后续可以把线性 attention、RWKV、RetNet 或 chunked state-space 实现放入同一代数模板比较。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 用幺半群除性和 wreath product 统一 RNN 表达能力争议，理论视角很清晰。
实验充分度: ⭐⭐⭐⭐☆ 作为理论论文，case study 足以支撑主张；但缺少更多现代架构的实例化分析。
写作质量: ⭐⭐⭐⭐☆ 结构严谨、定义完整，不过代数背景较重，非形式语言读者需要一定门槛。
价值: ⭐⭐⭐⭐⭐ 对 RNN/SSM 表达能力、有限精度理论和可复验架构分析都有长期参考价值。