arXiv cs.CL· Nikola Zubi\'c, Qian Li, Yuyi Wang, Davide Scaramuzza·· 12 小时前AI 评分31
有限精度循环模型何时因工具调用而增强表达能力？
When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?
AI 导读
研究将有限精度循环模型（含 B 位内部状态的 SSM）建模为与 oracle 交互的确定性有限状态控制器，分析工具访问何时提升表达能力。带记忆集 M 的有限状态有界接口工具可被内化，代价至多 ⌈log₂|M|⌉+O(1) 个循环比特；而单条无界纸带仅需局部 read/write/move 命令即可实现图灵完备，EQ_n 无工具时需 2^n 个状态，有纸带时仅需常数大小控制器。
正文 · AI 翻译
摘要：现代序列模型越来越多地被部署为智能体，将 token 生成与对外部工具的调用交错进行。我们研究这种工具访问何时会增加计算表达能力。我们将任何固定的有限精度循环序列模型（包括具有 $B$ 位内部状态的有限精度状态空间模型（SSM））建模为通过有限命令/观察接口与 oracle 交互的确定性有限状态控制器，并在所分析的两种机制之间建立分离。第一，每个具有记忆集 $M$ 的有限状态有界接口工具都可以以至多 $\lceil\log_2|M|\rceil+O(1)$ 个循环比特的代价被内化，因此组合系统仍保持有限状态。第二，仅具有局部 $\mathtt{read}$/$\mathtt{write}$/$\mathtt{move}$ 命令的单条无界纸带就足以实现图灵完备：每条具有状态集 $Q$ 和纸带字母表 $\Gamma$ 的单带图灵机都可由具有 $O(\log|Q|+\log|\Gamma|)$ 个循环比特的控制器模拟，而 $\mathrm{EQ}_n$ 在没有工具时需要 $2^n$ 个状态，但借助纸带只需一个恒定大小的控制器。第三，该构造由具有二值 one-hot 状态、$\{0,1\}$ 转移矩阵和零偏置的单层有限精度 \emph{选择性} 仿射 SSM 精确实现。在明确陈述的资源约定下，$O(\log B)$ 个循环比特足以对任何 $B$ 状态图灵机进行纸带辅助模拟，而在没有外部记忆的情况下，在一次精确仿射更新中直接实现任意 $B$ 状态转移映射需要总循环维度恰好为 $B-1$。固定描述大小、占用的纸带单元和交互成本与循环记忆分开报告。我们的结果关注确定性语义下的精确表达能力，而非可学习性或经验性能。
| 评论： | 25 页 |
| 主题： | 形式语言与自动机理论（cs.FL）；计算复杂性（cs.CC）；计算与语言（cs.CL） |
| 引用为： | arXiv:2607.06155 [cs.FL] |
| （或 arXiv:2607.06155v2 [cs.FL] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2607.06155 arXiv 颁发的 DOI 通过 DataCite |
|
| 期刊 参考： | 亚洲机器学习会议（ACML），2026 |
提交历史
来自：Nikola Zubić [查看电子邮件]
[v1]
2026 年 7 月 7 日星期二 11:32:56 UTC（32 KB）
[v2]
2026 年 10 月 21 日星期三 15:33:31 UTC（34 KB）
来源：arXiv cs.CL · arxiv.org