arXiv:2607.06155cs.FLcs.CC2026-07

有限精度循环模型加工具后何时能变强?答案是:只有用无限状态工具才可能实现图灵完备。

When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?

  • 将工具视为带有限接口的黑箱,分析其对模型计算能力的影响
  • 仅用一个支持读写移动的磁带工具,即可让模型模拟任意图灵机
  • 该能力由特定结构的轻量级模型实现,适合研究模型表达力边界

现代序列模型越来越多地作为代理,交替生成文本与调用外部工具。本文从架构层面精确分析了工具访问何时提升计算表达力。我们将任意固定精度的循环序列模型(包括具有 $B$ 位内部状态的有限精度状态空间模型)建模为一个确定性有限状态控制器,通过有限命令/观测接口与预言机交互。结果呈现清晰二分:第一,自身为有限状态的工具几乎无增益:通过产品状态模拟可内化任意有限记忆的有限接口预言机,仅需增加 $\ log_2 |M| + O(1)\$ 位,系统仍保持有限状态;第二,仅需一个最小的无限状态工具——即仅支持局部读、写、移动命令的磁带——即可使系统达到图灵完备:对任意单带图灵机(状态集 $Q$,带字母表 $Γ$),仅需 $O(\log |Q| + \log |Γ|)$ 位内部记忆的控制器即可模拟,并展示指数分离:无工具时 $\mathrm{EQ}_n$ 需 $2^n$ 状态,而单个常数大小控制器配合磁带工具即可解决;第三,该构造可被一个自然的一层有限精度选择性仿射状态空间模型精确实现,其隐藏状态为二值独热编码,转移矩阵取自 $\{0,1\}$,偏置为零,选择性在此构造中至关重要。附录中明确所有常数,证明了对 $B$-状态图灵机只需 $O(\log B)$ 递归位即可实现通用模拟,并给出匹配的不可行性结果。

原文摘要 · Abstract (English)

Modern sequence models are increasingly deployed as agents that interleave token generation with calls to external tools. We give an exact, architecture-level account of 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. Our results form a sharp dichotomy. First, tools that are themselves finite-state add essentially nothing: a product-state simulation internalizes any finite-state bounded-interface oracle with finite memory set $M$ at a cost of only $\log_2 |M| + O(1)$ additional bits, so the augmented system remains finite-state. Second, a single minimal infinite-state tool, namely a tape supporting only local $\mathtt{read}$, $\mathtt{write}$, and $\mathtt{move}$ commands, makes the system Turing complete: for every single-tape Turing machine with state set $Q$ and tape alphabet $Γ$, a controller with $O(\log |Q| + \log |Γ|)$ bits of internal memory simulates it, and we exhibit a concrete exponential separation: $\mathrm{EQ}_n$ requires $2^n$ states without tools but a single constant-size controller with the tape tool. Third, we show that this construction is realized exactly by a natural one-layer finite-precision selective affine SSM controller with binary one-hot hidden states, $\{0,1\}$ transition matrices, and zero biases. Selectivity is essential to the construction. In the supplementary material, we make all constants explicit, prove a logarithmic oracle-assisted universal simulation, where $O(\log B)$ recurrent bits suffice to simulate any $B$-state Turing machine, and prove a matching impossibility result.

计算理论模型表达力工具使用图灵完备

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。