arXiv cs.CL· Nikola Zubi\'c, Qian Li, Yuyi Wang, Davide Scaramuzza·· 13 小时前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 个状态，有纸带时仅需常数大小控制器。
正文 · 原文
Abstract:Modern sequence models are increasingly deployed as agents that interleave token generation with calls to external tools. We study when such tool access increases computational expressivity. We model any fixed finite-precision recurrent sequence model, including finite-precision state-space models (SSMs) with $B$ bits of internal state, as a deterministic finite-state controller interacting with an oracle through a finite command/observation interface, and establish a separation between the two regimes analyzed. First, every finite-state bounded-interface tool with memory set $M$ can be internalized at a cost of at most $\lceil\log_2|M|\rceil+O(1)$ recurrent bits, so the combined system remains finite-state. Second, a single unbounded tape with only local $\mathtt{read}$/$\mathtt{write}$/$\mathtt{move}$ commands suffices for Turing completeness: every single-tape Turing machine with state set $Q$ and tape alphabet $\Gamma$ is simulated by a controller with $O(\log|Q|+\log|\Gamma|)$ recurrent bits, and $\mathrm{EQ}_n$ requires $2^n$ states without tools but one constant-size controller with the tape. Third, this construction is realized exactly by a one-layer finite-precision \emph{selective} affine SSM with binary one-hot states, $\{0,1\}$ transition matrices, and zero biases. Under explicitly stated resource conventions, $O(\log B)$ recurrent bits suffice for tape-assisted simulation of any $B$-state Turing machine, whereas directly realizing an arbitrary $B$-state transition map in one exact affine update without external memory requires total recurrent dimension exactly $B-1$. Fixed description size, occupied tape cells, and interaction cost are reported separately from recurrent memory. Our results concern exact expressivity under deterministic semantics, not learnability or empirical performance.
| Comments: | 25 pages |
| Subjects: | Formal Languages and Automata Theory (cs.FL); Computational Complexity (cs.CC); Computation and Language (cs.CL) |
| Cite as: | arXiv:2607.06155 [cs.FL] |
| (or arXiv:2607.06155v2 [cs.FL] for this version) | |
| https://doi.org/10.48550/arXiv.2607.06155 arXiv-issued DOI via DataCite |
|
| Journal reference: | Asian Conference on Machine Learning (ACML), 2026 |
Submission history
From: Nikola Zubić [view email]
[v1]
Tue, 7 Jul 2026 11:32:56 UTC (32 KB)
[v2]
Wed, 21 Oct 2026 15:33:31 UTC (34 KB)
来源：arXiv cs.CL · arxiv.org