Skip to content

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

🕒 Published (v1): 2026-07-07 11:32 UTC · Source: Arxiv · link

Why this paper was selected

ETH Zurich; formal account of when tool use expands expressivity of sequence models — theoretical grounding for tool-augmented agents

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper gives an exact theoretical account of when external tool access increases the computational expressivity of finite-precision recurrent models (including SSMs). The central result is a sharp dichotomy: finite-state tools add essentially nothing, while a single minimal tape oracle makes any such system Turing complete with only \(O(\log|Q| + \log|\Gamma|)\) bits of internal controller memory.

Problem

Any fixed finite-precision recurrent model with \(B\) bits of internal state is equivalent to a finite-state machine recognizing only regular languages. Prior work showed chain-of-thought extends expressivity only in proportion to generated steps. The question of which tool interfaces actually escape this limitation—and at what memory cost—lacked a formal, architecture-level answer.

Method

The authors model any finite-precision recurrent model as a deterministic finite-state controller (up to \(2^B\) states) interacting with an oracle through finite command/observation alphabets. They then prove three classes of results:

  1. Finite-state oracle absorption: For any finite-state bounded-interface oracle with memory set \(M\), a product-state simulation internalizes it into the controller at a cost of \(\log_2|M| + O(1)\) additional bits—the augmented system stays finite-state.

  2. Tape oracle Turing completeness: A tape oracle supporting only local read/write/move commands (finite command alphabet, infinite tape memory) suffices for a controller with \(O(|Q||\Gamma|)\) states (i.e., \(O(\log|Q| + \log|\Gamma|)\) bits) to simulate any single-tape Turing machine \(T\) with state set \(Q\) and tape alphabet \(\Gamma\).

  3. SSM realization: Every observation-driven finite-state controller is exactly realized by a one-layer finite-precision selective affine SSM with one-hot binary hidden states, \(\{0,1\}\) transition matrices, and zero biases. Selectivity (input-dependent transition matrices) is essential.

In the supplementary, a logarithmic universal simulation is proved: \(O(\log B)\) recurrent bits suffice to simulate any \(B\)-state Turing machine by hard-coding the machine description in fixed parameters and copying it to tape. A matching impossibility result shows that without external memory, exactly realizing an arbitrary \(B\)-state transition map \(f:[B]\times\{0,1\}\to[B]\) in one affine recurrent update requires recurrent dimension exactly \(B-1\).

Key Contributions

  • Product-state simulation theorem: finite-state bounded-interface oracles are absorb­able into the controller; tool access adds only \(\log_2|M|+O(1)\) bits and does not change the language class.
  • Turing completeness via tape oracle: a finite-state controller plus local read/write/move tape access computes all partial computable functions, with \(O(\log|Q|+\log|\Gamma|)\) controller bits.
  • Concrete exponential separation: \(\mathrm{EQ}_n\) (equality on \(n\)-bit strings) requires \(\geq 2^n\) controller states without tools; a single constant-size controller with tape access solves all \(n\).
  • Exact SSM realization: the Turing-complete construction is realized by a one-layer selective affine SSM with hidden dimension \(O(|Q||\Gamma|)\); selectivity of the transition matrix is provably necessary.
  • Logarithmic universal simulation: \(O(\log B)\) recurrent bits suffice to simulate a \(B\)-state TM when the machine description is off-loaded to the tape (supplementary).
  • Impossibility for direct realization: without external memory, an exact one-step affine recurrent realization of an arbitrary \(B\)-state map requires recurrent dimension exactly \(B-1\), for any number of layers.

Results

  • EQn lower bound: any no-tool finite-state controller solving \(\mathrm{EQ}_n\) has \(\geq 2^n\) states (Theorem 9(i)); with tape access, a single constant-size controller solves all \(n\) (Theorem 9(ii)).
  • Tape-oracle memory cost: simulating a TM with state set \(Q\) and alphabet \(\Gamma\) requires only \(O(|Q||\Gamma|)\) controller states, or equivalently \(O(\log|Q|+\log|\Gamma|)\) bits.
  • Logarithmic universal simulation: \(O(\log B)\) recurrent bits simulate any \(B\)-state TM (vs. \(\Theta(B)\) bits without the tape, proven tight by the impossibility result).
  • SSM hidden dimension: one-layer selective SSM realizes the tape simulation with dimension \(d = O(|Q||\Gamma|)\); supplementary Theorem 19 reduces this to \(O(\log|Q|)\) under explicit resource conventions.
  • Three-symbol realization: an explicit constant \(C_0 = 9\) is given for the tape alphabet in Appendix A.

Limitations

  • All results concern worst-case expressivity, not learnability or generalization; no training or approximation arguments are made.
  • The tape oracle is infinite-state by design; practical tools (databases, calculators) may still be modeled as finite-state, which the theory classifies as adding nothing.
  • The SSM realization requires selectivity (input-dependent \(A_t\)); the result does not apply to linear time-invariant (LTI) SSMs with a fixed transition matrix.
  • The logarithmic universal simulation offloads the machine description to fixed readout parameters—this resource accounting convention is explicit but may not match all practical SSM cost models.
  • Results are about finite-precision models; the connection to actual floating-point behavior of trained models is not addressed.

Relevance to Agentic AI / LLM Agents

This paper provides the first rigorous formal foundation for a question central to agentic LLM design: which tools actually extend what a model can compute? The dichotomy—finite-state tools (retrievers, bounded caches) add nothing expressively, while unbounded memory tools (scratchpads, code interpreters with persistent state) confer Turing completeness—gives practitioners a principled classification of tool types. For SSM-based agents specifically, the result shows that selectivity plus a tape-like external memory is the minimal architectural combination that breaks the regular-language ceiling, which directly informs how to architect memory and tool interfaces in agentic systems. The logarithmic memory savings (\(O(\log B)\) vs. \(\Theta(B)\) bits) quantify the advantage of off-loading computation to external tools, validating the practical intuition behind scratchpad and code-execution augmentation.