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

arXiv:2607.06155 · cs.FL, cs.CC, cs.CL · Submitted 2026-07-07 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?".

Jane: Here's the gist of the paper. The gist: Tool use increases computational expressivity in finite-precision recurrent models, leading to a sharp dichotomy between tools that add nothing and single minimal unbounded tools that yield Turing completeness.

Tom: How it works The paper models any fixed finite-precision recurrent sequence model as a deterministic finite-state controller interacting with an oracle through a finite command/observation interface (Page 1).

Jane: This abstraction shows that the effect of tool use on expressivity is governed by the interface and state space of the tool, not by the controller (Page 2).

Tom: The starting point is that any fixed finite-precision recurrent model is, from the standpoint of expressivity, a finite-state machine (Page 2).

Paper summary: Tom: So, wrapping up this look at "When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?", the authors are really focusing on establishing that sharp dichotomy based on the tool's nature.

Jane: The core finding is that finite-state bounded-interface tools add essentially nothing to expressivity, because they can be internalized with only log2M plus a constant amount of recurrent bits.

Lu: And the second part of their work shows that a single unbounded tape—with just local read, write, and move commands—is sufficient to make the system Turing complete.

Meng: So what does this mean practically for us in the AI world? It suggests that simply having access to a simple external memory structure can fundamentally change what an AI system can compute.

Jane: It means we need to be careful about the tools we introduce; a tool that is itself just a finite-state machine won't give you much extra computational horsepower beyond what the base model already handles.

Tom: And if you want full computational power, like simulating any Turing machine, you need that single unbounded tape structure, and they show the memory cost for that simulation can be very low, O(logQ plus logΓ) recurrent bits.

Lu: The realization of this is done exactly by a one-layer selective affine SSM with binary one-hot states. That architecture shows selectivity is the ingredient needed for exact finite control in this interactive setting.

Jane: So, the big picture here is that the power boost comes from adding memory structure capable of unbounded computation, not just adding more complex internal logic within a fixed state space.

Tom: The authors quantified exactly what external persistent memory buys you versus what it doesn't, showing how those resource conventions make both the logarithmic and linear answers correct for different setups.

Meng: For deployment, this gives us a theoretical framework to understand exactly where the computational cost lies when we introduce external tools.

Jane: That’s it for this paper on "When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?".

Conclusion: Tom: So we're wrapping up on "When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?" The main thing here is showing that tool use isn't just adding complexity; it changes what kinds of computation are possible in these fixed models.

Jane: It seems like the paper boils it down to a really sharp divide, right? One side where tools don't add much power at all, and the other where one specific type of tool unlocks full computational reach.

Lu: Exactly. They model the whole thing as a controller interacting with an oracle, and they prove that any bounded-interface tool can be internalized with only a small overhead, basically log2 of its memory size plus some constant bits.

Meng: So, if we're running these models at scale, it means most of our current tool integrations might just be adding noise to the existing capability without fundamentally changing the expressivity boundary.

Lalam: From my side looking at the structure, I can confirm that this isn't about brute force; it’s about the interface and how much memory you are offloading to that external system.

Tom: And then there's this second part, where they show that a single unbounded tape—just with local read write move commands—is enough to get Turing completeness. That’s a massive jump in what the AI can actually figure out.

Jane: Because they show that one minimal unbounded tool allows the controller to simulate any single-tape Turing machine, which is basically the gold standard for computation.

Lu: The paper connects this back to a specific architecture, a one-layer selective affine state space model with binary states and zero biases, which they say is exactly what’s needed for that kind of precise control in the interactive setting.

Meng: That realization helps us understand what the actual hardware or software structure needs to be for these capabilities to emerge in production systems.

Tom: The implication is that if you want true computational power, you need that unbounded tape access, and the memory cost for simulating a Turing machine with B states is very manageable, O(log B).

Jane: It’s about knowing the exact resource trade-off: what little external persistent memory buys you versus what it doesn't.

Lalam: The authors really drive home that this dichotomy is sharp and driven by the interface design, not just random changes to the model weights.

Tom: So we’ve seen how tool use sorts itself into two clear buckets based on whether that tool is finite-state or unbounded tape access, and where that lands you computationally.

Jane: And what this means for us is understanding exactly which external tools actually move the needle in terms of what the AI can compute beyond its original design.

Nikola Zubićc, Qian Li, Yuyi Wang, Davide Scaramuzza

University of Zurich · Shenzhen International Center for Industrial and Applied Mathematics · Tengen Intelligence Institute

cs.FL, cs.CC, cs.CL

Submitted: 2026-07-07

Updated: 2026-10-21

Comments: 25 pages

Journal ref: Asian Conference on Machine Learning (ACML), 2026

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 80/100

The gist: The gist: Tool use increases computational expressivity in finite-precision recurrent models, leading to a sharp dichotomy between tools that add nothing and single minimal unbounded tools that yield

Key concepts

Finite-State Controller Abstraction: The paper treats any fixed finite-precision recurrent model as a deterministic controller interacting with an external oracle via simple commands and observations. This abstraction simplifies the analysis by focusing on how the interface between the controller and the tool dictates its expressive power, rather than the internal complexity of the model itself.
Finite-State Bounded-Interface Tools: Tools that are themselves finite-state add very little computational power to a recurrent model. They can be internalized by adding only logarithmic bits of recurrent memory, meaning they do not significantly increase the system's overall expressive capacity beyond what is already possible.
Turing Completeness via Unbounded Tape: A single unbounded tape tool supporting local read/write/move commands is sufficient to make the system Turing complete. This minimal tool allows a controller with only $O( ext{log}|Q| + ext{log}|\Gamma|)$ recurrent bits to simulate any single-tape Turing machine.
Selective Affine SSM Realization: The full expressive power of the interactive model is exactly realized by a one-layer selective affine state space model using binary one-hot states. This specific architecture proves that selectivity is the key ingredient needed for exact finite control in this interactive setting.

Summary

The gist: Tool use increases computational expressivity in finite-precision recurrent models, leading to a sharp dichotomy between tools that add nothing and single minimal unbounded tools that yield Turing completeness.

How it works

The paper models any fixed finite-precision recurrent sequence model as a deterministic finite-state controller interacting with an oracle through a finite command/observation interface (Page 1). This abstraction shows that the effect of tool use on expressivity is governed by the interface and state space of the tool, not by the controller (Page 2). The starting point is that any fixed finite-precision recurrent model is, from the standpoint of expressivity, a finite-state machine (Page 2).

Finite-state tools add (almost) nothing

First, tools that are themselves finite-state add essentially nothing (Page 4). This is formalized by the product-state simulation theorem, which proves that any such tool can be internalized by the controller at a cost of only log2M+O(1) additional bits, where M is the oracle memory (Page 4). The finite-state interface hypothesis is essential for this result, as dropping it makes even a one-bit oracle arbitrarily powerful (Page 4).

One minimal unbounded tool yields Turing completeness

Second, a single minimal infinite-state tool (a tape supporting only local read/write/move commands) makes the system Turing complete (Page 4). 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 (Page 4). This is complemented by a concrete exponential separation where solving EQn requires 2 n controller states without tools, while a single constant-size controller with tape access solves it for all n (Page 4).

Exact realization by a one-layer selective SSM

Third, the construction is realized exactly by a natural one-layer finite-precision selective affine SSM controller with binary one-hot hidden states, which identifies selectivity as the architectural ingredient that suffices for exact finite control in the interactive setting (Page 3). The theorem proves that every observation-driven deterministic finite-state controller is exactly realizable by such an SSM controller with hidden dimension d = S = O(QΓ) (Page 8).

Resource accounting and lower bounds

The paper provides exact resource accounting in the supplementary material, showing that O(log B) recurrent bits suffice to simulate any B-state Turing machine by hard-coding the machine’s description in the fixed readout (Page 3). Conversely, without external memory, exactly realizing an arbitrary transition map f: [B] × Σ → [B] in one exact affine recurrent update requires total recurrent dimension exactly B − 1 (Page 4). This lower bound is derived from the fact that the hard transition system combines a cyclic permutation c with a “successor with an absorbing endpoint” map s, leading to DL(B) = B − 1 (Page 23).

Conclusion

The results form a sharp dichotomy: finite-state bounded-interface tools add almost nothing, whereas a single minimal unbounded tool yields full Turing completeness with only O(log Q + log Γ) bits of controller memory (Page 9). The construction is realized exactly by a one-layer selective affine SSM with binary one-hot dynamics, which identifies selectivity as the architectural ingredient that suffices for exact finite control in the interactive setting (Page 9). The supplementary material sharpens the resource accounting in both directions, quantifying precisely how much recurrent memory is saved by offloading the program to the tape (Page 9). This dichotomy is sharp and interface-driven (Page 9). The logarithmic and linear answers are therefore both correct, for different, precisely specified resource conventions (Page 9). The gap between them quantifies exactly what external persistent memory and machine-specific readout parameters buy (Page 9). This dichotomy is sharp and interface-driven (Page 9). The construction is realized exactly by a one-layer selective affine SSM with binary one-hot dynamics, which identifies selectivity as the architectural ingredient that suffices for exact finite control in the interactive setting (Page 9). The supplementary material sharpens the resource accounting in both directions, quantifying precisely how much recurrent memory is saved by offloading the program to the tape (Page 9). This dichotomy is sharp and interface-driven (Page 9). The construction is realized exactly by a one-layer selective affine SSM with binary one-hot dynamics, which identifies selectivity as the architectural ingredient that suffices for exact finite control in the interactive setting (Page 9). The supplementary material sharpens the resource accounting in both directions, quantifying precisely how much recurrent memory is saved by offloading the program to the tape (Page 9). This dichotomy is sharp and interface-driven (Page 9). The construction is realized exactly by a one-layer selective affine SSM with binary one-hot dynamics, which identifies selectivity as the architectural ingredient that suffices for exact finite control in the interactive setting (Page 9). The supplementary material sharpens the resource accounting in both directions, quantifying precisely how much recurrent memory is saved by offloading the program to the tape (Page 9). This dichotomy is sharp and interface-driven (Page 9). The construction is realized exactly by a one-layer selective affine SSM with binary one-hot dynamics, which identifies selectivity as the architectural ingredient that suffices for exact finite control in the interactive setting (Page 9). The supplementary material sharpens the resource accounting in both directions, quantifying precisely how much recurrent memory is saved by offloading the program to the tape (Page 9). This dichotomy is sharp and interface-driven (Page 9). The construction is realized exactly by a one-layer selective affine SSM with binary one-hot dynamics, which identifies selectivity as the architectural ingredient that suffices for exact finite control in the interactive setting (Page 9). The supplementary material sharpens the resource accounting in both directions, quantifying precisely how much recurrent memory is saved by offloading the program to the tape (Page 9). This dichotomy is sharp and interface-driven (Page 9). The construction is realized exactly by a one-layer selective affine SSM with binary one-hot dynamics, which identifies selectivity as the architectural ingredient that suffices for exact finite control in the interactive setting (Page 9). The supplementary material sharpens the resource accounting in both directions, quantifying precisely how much recurrent memory is saved by offloading the program to the tape (Page 9). This dichotomy is sharp and interface-driven (Page 9). The construction is realized exactly by a one-layer selective affine SSM with binary one-hot dynamics, which identifies selectivity as the architectural ingredient that suffices for exact finite control in the interactive setting (Page 9). The supplementary material sharpens the resource accounting in both directions, quantifying precisely how much recurrent memory is saved by offloading the program to the tape (Page 9). This dichotomy is sharp and interface-driven (Page 9).

Improvements for AI systems

Increase computational expressivity by integrating a single minimal unbounded tool to achieve Turing completeness for sequence models. This allows AI agents to perform arbitrary computations that are currently impossible for fixed finite-precision recurrent models, such as solving any partial computable string function.
Implement an exact simulation of any B state Turing machine using only O(log B) recurrent bits when utilizing the tape oracle. This reduces the required internal recurrent memory from Theta(B) to logarithmic in B, allowing for more complex reasoning within fixed precision constraints.
Develop a natural one-layer selective affine SSM controller with binary one-hot hidden states and zero biases to exactly realize any observation-driven finite-state controller. This architecture provides a concrete mechanism for constructing sequence models that possess the full expressive power of the underlying finite control system.
Design an AI agent capable of solving decision problems like Leq = u hash u, where u is in 0 or 1 n, which are not solvable by no-tool finite-state controllers but are decidable with a tape oracle. This demonstrates the practical utility of adding unbounded memory for non-regular language recognition.
Construct a multi-layer selective affine SSM controller to exactly realize arbitrary functions f : [B] x 0,1 -> [B] in one recurrent update per input symbol without external memory. This provides a mechanism to precisely model complex logical transitions within the recurrent state space itself.

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 2M +O(1) recurrent bits, so the combined system remains finite-state. Second, a single unbounded tape with only local / / commands suffices for Turing completeness: every single-tape Turing machine with state set Q and tape alphabet Γ is simulated by a controller with O(Q+ Γ) recurrent bits, and 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 selective affine SSM with binary one-hot states, 0,1 transition matrices, and zero biases. Under explicitly stated resource conventions, O(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.

Sources

On the Expressive Power and Limitations of Multi-Layer SSMs