MinMax Recurrent Neural Cascades¶
会议: NeurIPS 2026
arXiv: 2605.06384
OpenReview: https://openreview.net/forum?id=8sPcuoX2cj
领域: 其他
关键词: 循环神经网络, MinMax 代数, 自动机表达力, 并行前缀扫描, 梯度不消失
一句话总结¶
提出基于 MinMax 半环代数的新型循环神经网络级联架构（MinMax RNC），在保持 \(O(\log T)\) 并行前缀扫描高效计算与状态有界稳定性的同时，实现了对正则语言的完全表达力，并在长程序列反向传播中保持状态梯度严格不消失。
研究背景与动机¶
循环神经网络（RNN）依靠隐状态维持对历史上下文的记忆，是序列建模中最直观的形式，但长期受困于随序列增长的状态与梯度爆炸/消失问题。传统非线性 RNN（如经典 Elman RNN、LSTM、GRU）虽然具备表达正则语言的理论潜力，但在数值训练中面临梯度消失瓶颈，且因非线性依赖而无法实现时间维度的并行化训练。近年来以 Mamba、RWKV、xLSTM 为代表的线性循环模型通过将递推关系松弛为可结合的矩阵乘加运算，成功利用并行前缀扫描（Parallel Scan）突破了序列并行瓶颈，并在经验性能上媲美 Transformer。
然而，现有线性循环模型在理论表达力与鲁棒性之间存在内在矛盾。理论表明，标准线性循环架构若要识别无星语言（star-free languages），往往依赖脆弱的数值状态轨迹——即不同状态序列在有限步内收敛至极端狭窄的间隙。当引入度量自动机理论中的 \(\eta\)-有限性（\(\eta\)-finiteness，要求状态空间与决策边界具有非零安全裕度以排除数值病态解）时，线性模型如 Mamba 便失去了识别全部无星语言的能力；相反，非线性模型（如 sLSTM）虽保留了表达力却牺牲了对数深度的并行扫描能力。这表明现有线性循环与非线性循环处于“计算并行度”与“鲁棒形式表达力”的不可兼得困境。
本文的切入角度是探索一种既具备半环结合律以支持并行扫描、又具备非线性选择能力以实现离散逻辑状态转移的新代数结构。核心 idea：将传统线性递推中的加法替换为最大值运算（\(\max\)）、乘法替换为最小值运算（\(\min\)），构建基于 MinMax 代数的循环神经级联架构（MinMax RNC），实现全正则语言表达力、对数并行复杂度、状态与损失梯度全局有界、以及恒为单位范数的非消失状态梯度的统一。
方法详解¶
整体框架¶
MinMax Recurrent Neural Cascades（MinMax RNC）由多层循环层级联组成。每一层包含若干并行排布的 MinMax Recurrent Unit（最小最大循环单元），单元的参数化重置矩阵与置位向量由前馈神经网络（带有 LayerNorm 与残差连接的 MLP）动态生成。整个模型接收输入序列 \(u_1, \dots, u_T\)，以 MinMax 代数规则在隐状态空间中递推，再由输出投影映射到下一层或最终输出。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入序列 ut"] --> B["前馈控制器与门控变换<br/>MLP生成重置矩阵Rt与置位向量st"]
B --> C["MinMax代数循环递推<br/>xt = (Rt ⊗ xt-1) ⊕ st"]
C --> D["双模态并行求值调度<br/>结合律半环算子⊕⊗支持前缀扫描"]
D --> E["层级级联与残差投影<br/>LayerNorm + MLP多层堆叠输出yt"]关键设计¶
1. MinMax 代数循环单元：非线性离散选择与恒等保持机制 传统线性循环依靠加权求和更新状态，无法精确维持变量的常数截断与状态交换。MinMax 循环单元在实数标量域定义两元算子 \(a \oplus b := \max(a, b)\) 和 \(a \odot b := \min(a, b)\)。对于输入 \(u_t\)，网络计算重置矩阵 \(R(u_t) \in \mathbb{R}^{n \times n}\) 与置位向量 \(s(u_t) \in \mathbb{R}^n\)，状态更新方程定义为： $\(x_t = (R(u_t) \otimes x_{t-1}) \oplus s(u_t)\)$ 其中矩阵乘法 \((A \otimes B)_{i,j} = \max_k (A_{i,k} \odot B_{k,j})\)。在标量状态（\(n=1\)）情况下，递推变为 \(x_t = \max(\min(r_t, x_{t-1}), s_t)\)。当 \(s_t \le r_t\) 时，若隐状态满足 \(x_{t-1} \in [s_t, r_t]\)，则变换退化为严格的恒等映射 \(x_t = x_{t-1}\)，实现信息的无损锁定；当输入触发状态重置时，只要控制 \(r_t < s_t\)，状态立即被置为常数值 \(s_t\)。该机制从代数层面原生支持了有限半自动机的恒等-重置（identity-reset）行为。
2. 自动机级联分解与有限状态表达力 根据代数自动机理论（Algebraic Automata Theory）与 Krohn-Rhodes 分解定理，任何正则语言所对应的半自动机均可分解为恒等-重置半自动机与置换半自动机（permutation semiautomata）的级联。MinMax 单元的状态维度 \(d_{\text{state}}\) 精确对应于其能够模拟的置换半自动机的置换度（permutation degree）。标量状态（\(d_{\text{state}}=1\)）单元由于其递推在任意常数输入下至多两步收敛，无法实现非平庸置换，因此其级联网络在 \(\eta\)-有限性约束下精确对应全部无星语言（即群无关正则语言，Group-free regular languages）；而当状态维度扩展为 \(n\) 时，矩阵乘法 \(R \otimes x\) 可以通过在置换位置赋大值、其余位置赋极小值实现任意 \(n\) 元置换。因此，任意具有置换度 \(n\) 的正则函数都可以被状态度为 \(n\) 的 MinMax RNC 严格实现，在理论上达到了有限内存系统表达力的上界。
3. 半环结合律与并行前缀扫描复杂度 循环网络的一大瓶颈是时序串行依赖。由于算子 \(\odot\) 对 \(\oplus\) 满足完全分配律，且两者均满足结合律与交换律，复合循环步的映射同样构成幺半群。定义状态变换 \(\tau_t(x) = (R_t \otimes x) \oplus s_t\)，两次连续变换的复合满足 \(\tau_{t+1}(\tau_t(x)) = (R_{t+1:t} \otimes x) \oplus s_{t+1:t}\)，对应的矩阵-向量复合算子为： $\(\langle R', s' \rangle \oplus_{\otimes} \langle R, s \rangle := \langle R' \otimes R, (R' \otimes s) \oplus s' \rangle\)$ 该复合运算 \(\oplus_{\otimes}\) 具备严格结合律，使得长为 \(T\) 的序列求值可以通过并行前缀扫描（Parallel Scan）完成。对于序列长度 \(T\) 与单元状态维度 \(d_{\text{state}}\)，串行评估时间复杂度为 \(O(T \cdot d_{\text{state}}^2)\)，而并行扫描可在深度 \(O(\log T \cdot \log d_{\text{state}})\) 及总工作量 \(O(T \cdot d_{\text{state}}^3)\) 内完成，使固定规模的 MinMax RNC 达到对数时间复杂度 \(O(\log T)\)。
4. 分段解析函数的有界性与恒定单位范数反向传播 针对循环网络梯度的长期衰减，MinMax 运算展现出独特的“分段线性刚性”。首先，由于输入与参数处于有界闭集，且 MinMax 算子仅在输入集合中取最值或传播前值，系统天然满足有界输入有界状态（BIBS）与有界输出（BIBO）稳定性。其次，在分段解析函数（PAP）框架下，\(\min\) 与 \(\max\) 的次微分/超微分表现为将活跃极值变量分配归一化权重。当初始状态落在无冲突活跃区间 \(x_0 \in (\max_t s_t, \min_t R_t)\) 内时，\(x_{t-1}\) 在每一步均是 \(\min\) 与 \(\max\) 运算中的唯一活跃变量。此时链式法则中每步状态偏导数严格为 1： $\(\nabla_{x_{t-1}} x_t = 1 \implies \nabla_{x_0} x_t = \prod_{k=1}^t 1 = 1\)$ 这一结论从数学上彻底根除了长时序中的梯度衰减，使模型在跨越百万步长时仍能有效回传监督信号。
损失函数 / 训练策略¶
对于合成自动机与字符任务，采用标准交叉熵损失；对于语言建模，采用自回归 Next-Token 预测损失。训练优化器采用标准 Adam，学习率设为 \(10^{-3}\)，配合阶梯衰减调度（每 5 个 epoch 衰减为原来的 0.5），权重衰减 \(\lambda = 10^{-4}\)。在工程实现上，针对 GPU 显存与计算密度特性，系统交替使用并行扫描与小块串行计算以支持任意长度序列的吞吐优化。
实验关键数据¶
主实验¶
论文在三项关键的群无关（Group-free）合成基准上评估长度泛化能力（训练长度 \(\le 512\)，验证长度 \(\le 2048\)，外推评估长度达 \(2^{10} \times 1024 \approx 10^6\)），对比当前主流的线性循环架构（Mamba、xLSTM-L、mLSTM）与非线性循环架构（sLSTM）。模型参数量均控制在 \(\sim 125\text{k}\) 水平。
| 基准任务 (Benchmark) | 参数设置 \(n\) | MinMax RNC (本文) | Mamba | xLSTM-L | mLSTM | sLSTM |
|---|---|---|---|---|---|---|
| Latching(\(2n\)) | \(n \in \{2, \dots, 9\}\) | 100.0% | 54.3% | 8.2% | 7.4% | 28.2% |
| Sequences(\(n\)) | \(n \in \{2, 3, 4, 8, 16\}\) | 100.0% | 46.5% | 46.5% | 44.5% | 46.5% |
| InductionHeads(16) | \(M=16\) | 100.0% | 100.0% | 6.7% | 6.5% | 6.2% |
| InductionHeads(30) | \(M=30\) | 100.0% | 3.5% | 3.1% | 3.0% | 3.0% |
在真实文本数据上，作者训练了 112M 参数的自回归 MinMax RNC（12 层，隐藏维度 728，1456 个单元，标量状态 \(d_{\text{state}}=1\)），在 OpenWebText 上达到 3.12 的验证困惑度损失，与同等规模的 OpenAI GPT-2 124M 评测结果（3.12）完全持平。
消融实验¶
针对 MinMax RNC 架构中门控机制（输出门 OG）、卷积变换类型（门控卷积 GC 与基础卷积 basic）以及参数初始化策略（不对称初始化 asymmetric、Kaiming、小尺度初始化 small_init）在不同任务收敛性上的消融分析：
| 配置代号 | 架构参数 (层数, 状态维, OG, 卷积, 初始化) | Latching(512) 成功率 (95% CI) | Sequences(16) 成功率 (95% CI) | InductionHeads(30) 成功率 (95% CI) |
|---|---|---|---|---|
| 基础门控小初化 | (2, 40, F, basic, small_init) | 10/10 (0.72, 1.00) | 10/10 (0.72, 1.00) | 7/10 (0.40, 0.89) |
| 门控卷积小初化 | (2, 40, F, gated, small_init) | 10/10 (0.72, 1.00) | 10/10 (0.72, 1.00) | 7/10 (0.40, 0.89) |
| 输出门控小初化 | (2, 40, T, basic, small_init) | 10/10 (0.72, 1.00) | 10/10 (0.72, 1.00) | 7/10 (0.40, 0.89) |
| 不对称置位初始化 | (2, 40, T, basic, asymmetric) | 10/10 (0.72, 1.00) | 10/10 (0.72, 1.00) | 9/10 (0.60, 0.98) |
| 扩展状态维不对称初化 | (2, 90, T, basic, asymmetric) | 10/10 (0.72, 1.00) | 10/10 (0.72, 1.00) | 10/10 (0.72, 1.00) |
关键发现¶
- 完美长度外推：在 Latching 和 Sequences 任务中，所有基线模型在训练长度（512）内均能达到近 100% 精度，但在外推至 \(10^6\) 步时迅速崩溃至 \(2\% \sim 50\%\)，而 MinMax RNC 在全部评测长度上始终保持 100.0% 的零误差外推。
- 归纳头扩展瓶颈：Mamba 在小批次（\(bs=8\)）下虽可解决 InductionHeads(16)，但在候选词增加到 \(M=30\) 时精度暴跌至 3.5%；而 MinMax RNC 凭借确定性的状态留存机制完美维持 100% 准确率。
- 不对称初始化的重要性：消融实验显示，在置位与重置信号（set/reset）上采用不对称初始化，能显著加速模型学习精确常数截断与状态保持的能力，将 InductionHeads(30) 的多随机种子训练收敛率提升至 90% 以上。
亮点与洞察¶
- 代数结构的精妙置换：用 \((\max, \min)\) 代替传统线性系统的 \((+, \times)\)，巧妙借助分配律和结合律保全了并行前缀扫描能力，同时天然获得了非线性选择与离散状态锁定特性。
- 理论与经验的完全闭环：从代数自动机理论严格推导了状态维数与置换度的对应关系，直接证明了标量 MinMax 单元足以拟合全部无星语言，并用外推实验印证了数学性质。
- 极小状态维度的硬件优势：在与 Mamba 和 xLSTM 同等参数量下，MinMax RNC 单层仅需极少的状态标量（如 \(d_{\text{state}}=40\)），大幅降低了训练与推理期间的显存占用和通信带宽。
局限与展望¶
- 实际语言模型规模有限：目前自回归语言建模验证仅停留在 112M 参数规模，在十亿以上参数级的大语言模型预训练中，极端最值选择是否会导致表征坍缩或训练不稳定仍待验证。
- 不可微点的理论边缘情况：虽然在 PAP 理论下梯度几乎处处存在，但在数值实现中多分支相等的不可微边界依赖次微分选择约定，可能在高度复杂的混合任务中产生局部优化震荡。
- 与注意力机制的混合潜力：纯 MinMax 架构适合处理逻辑强相关的离散状态追踪，未来与注意力或卷积机制结合构建混合架构是极具前景的方向。
相关工作与启发¶
- vs Mamba / S4: 线性状态空间模型采用连续状态矩阵离散化与加权求和，虽然能高效并行计算，但在有限精度裕度（\(\eta\)-finiteness）下无法稳固保持离散状态；MinMax RNC 通过 \((\max, \min)\) 运算实现无损状态锁定，且兼顾 \(O(\log T)\) 并行复杂度。
- vs sLSTM / mLSTM: sLSTM 采用指数门控与非线性归一化，具备出色的形式语言表达力但无法执行时间维度的前缀扫描；mLSTM 采用外积矩阵内存支持并行但难以完美表达无星语言。MinMax RNC 成功在单一架构中融合了 sLSTM 的表达力与 mLSTM 的并行性。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次将 MinMax 半环代数引入现代循环神经网络架构设计，理论视角独树一帜。
- 实验充分度: ⭐⭐⭐⭐☆ 理论证明极其详尽严密，合成基准与外推实验无懈可击，真实语言模型预训练已有扎实初验。
- 写作质量: ⭐⭐⭐⭐⭐ 数学形式化表达清晰，代数自动机与动力系统理论衔接严丝合缝。
- 价值: ⭐⭐⭐⭐⭐ 为长上下文序列建模与循环架构理论提供了突破性的全新代数范式。