💬 NLP

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

This paper establishes a sharp dichotomy demonstrating that while finite-state tools add negligible computational power to finite-precision recurrent models, a single minimal infinite-state tool (a read-write tape) renders them Turing complete, a capability concretely realized by selective affine state-space models.

Original authors: Nikola Zubić, Qian Li, Yuyi Wang, Davide Scaramuzza

Published 2026-07-08

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Nikola Zubić, Qian Li, Yuyi Wang, Davide Scaramuzza

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, but slightly forgetful robot. This robot is a "Finite-Precision Recurrent Model." In plain English, it's a computer program that processes information step-by-step, but it has a tiny, fixed amount of memory (like a notepad with only 100 squares). Because its memory is so small and fixed, this robot is limited: it can only solve simple, repetitive patterns. It cannot count to infinity, remember a long story, or solve complex puzzles that require looking back and forth.

The paper asks a simple question: What happens if we give this forgetful robot a tool?

The authors discovered that the answer depends entirely on what kind of tool you give it. They found a sharp "either/or" split:

1. The "Finite" Tool: A Tiny Calculator

Imagine you give your robot a calculator that can only do basic math and has a tiny screen that shows one number at a time.

The Result: The robot doesn't get much smarter. It just has to spend a tiny bit of its own memory to remember what the calculator is doing.
The Analogy: It's like giving a person with a small memory a post-it note. They can write one thing down, but they still can't solve a complex mystery. The robot remains "finite-state." It can still only do simple, repetitive tasks.
The Paper's Claim: If the tool itself has a limited memory and a limited set of commands, the robot can just "copy" the tool's memory into its own head. It gains almost no new power.

2. The "Infinite" Tool: An Infinite Tape

Now, imagine you give the robot a tape (like an old-school cassette tape or a scroll of paper) that is infinitely long. The robot can only do three things with it:

Read the symbol under the current spot.
Write a new symbol.
Move the head one step left or right.

The Result: Suddenly, the robot becomes a genius. It can solve any problem that can be solved by a computer, no matter how complex. It becomes "Turing Complete."
The Analogy: It's like giving a person with a small memory a library. Even though their brain is small, they can walk back and forth in the library, reading and writing notes on the shelves. They can now solve the hardest math problems, write novels, or crack codes. The "infinite tape" acts as an external brain.
The Paper's Claim: Just one of these simple, infinite tapes is enough to turn a simple robot into a universal computer. The robot only needs a tiny bit of internal memory (just enough to remember where it is on the tape and what it's currently thinking) to control this infinite power.

The "Magic" Ingredient: Selectivity

The paper also shows that this isn't just theoretical; it works with a specific type of modern AI architecture called a Selective State-Space Model (SSM).

The Analogy: Think of a standard robot as a train on a fixed track. It always moves the same way. A "Selective" robot is like a train that can change its tracks based on what it sees right in front of it.
The authors proved that if you give this "track-changing" robot a tiny bit of memory and an infinite tape, it can perfectly simulate any computer program. The "selectivity" (changing behavior based on input) is the key that unlocks the door to infinite power.

The "Equality" Test (A Concrete Example)

To prove this, the authors used a specific test: Checking if two long strings of numbers are identical.

Without a tool: If the strings are 1,000 digits long, the robot needs a brain with 1,000 digits of memory to check them. If the strings are 1 million digits long, it needs a million digits of memory. It's impossible for a small robot.
With the tape tool: The robot can write the first string on the tape, then walk back and forth comparing it to the second string. It only needs a tiny amount of internal memory to remember "I am comparing digit #500." The tape does the heavy lifting.

Summary

The paper concludes that tools don't make AI smarter just by existing.

If the tool is small and limited, the AI stays limited.
If the tool is an infinite memory tape (even with very simple commands), the AI becomes infinitely powerful, provided it has a specific "selective" mechanism to control the tape.

This gives us a precise map of exactly how much "brain power" (internal memory) an AI needs when it is allowed to use external tools. It turns out you don't need a giant brain if you have a giant notebook.

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

Problem Statement

Modern sequence models are increasingly deployed as agents that interleave token generation with calls to external tools (e.g., calculators, code interpreters, retrieval systems). While empirical success is evident, a fundamental theoretical question remains unanswered: Which specific tools increase the computational expressivity of a fixed finite-precision recurrent model, by how much, and at what internal memory cost?

Existing literature establishes that fixed finite-precision recurrent models (including State-Space Models or SSMs) are equivalent to finite-state machines (FSMs) and recognize only regular languages. Chain-of-thought decoding offers limited gains constrained by the number of generated steps. This paper seeks to provide an exact, architecture-level characterization of how external tool access alters this computational landscape, distinguishing between tools that merely add bounded memory and those that fundamentally expand computational power.

Methodology

The authors abstract the sequence model as a deterministic finite-state controller interacting with an oracle through a finite command/observation interface.

Controller Model: A controller with $B$ bits of internal state is modeled as an FSM with at most $2^B$ configurations. It reads an input, then enters a generation phase where it emits tokens, issues tool commands, receives observations, or halts.
Tool Interfaces: The paper analyzes two distinct classes of tools:
1. Finite-State Bounded-Interface Oracles: Tools with finite memory sets and finite command/observation alphabets.
2. Unbounded Tape Oracles: A minimal infinite-state tool supporting local read/write/move operations on an unbounded tape (analogous to a Turing machine tape).
Realization: The theoretical constructions are mapped to finite-precision selective affine SSMs. The authors prove that any observation-driven finite-state controller can be exactly realized by a one-layer SSM with binary one-hot hidden states, $\{0, 1\}$ transition matrices, and zero biases, provided the transition matrices are selective (dependent on the current observation token).

Key Contributions and Results

1. Finite-State Tools Add (Almost) Nothing

The paper establishes a "product-state simulation" theorem. If a tool is itself a finite-state machine with memory set $M$ and a finite interface, the controller can internalize the tool's state.

Result: The augmented system remains a finite-state machine. The internal memory cost increases by only $\log_2 |M| + O(1)$ bits.
Implication: Finite-state tools do not increase the class of recognizable languages beyond regular languages. The finite-state nature of the interface is essential; arbitrary initialization or command-to-observation maps could otherwise encode non-regular behavior.

2. One Minimal Unbounded Tool Yields Turing Completeness

The authors define a "tape oracle" supporting only local read/write/move commands.

Result: A controller with $O(\log |Q| + \log |\Gamma|)$ bits of internal memory (where $Q$ is the set of Turing machine states and $\Gamma$ is the tape alphabet) can simulate any single-tape Turing machine when interacting with this tape oracle.
Turing Completeness: The system becomes Turing complete. The controller does not need to store the tape; it only needs to store the current state of the simulated machine and the mode of operation.
Concrete Separation: The paper provides a concrete exponential lower bound using the equality problem $EQ_n$ $E Q_{n}$ (checking if two $n$ $n$ -bit strings are equal).
- Without tools: Solving $EQ_n$ requires a controller with at least $2^n$ states.
- With tape access: A single constant-size controller (independent of $n$ ) can solve $EQ_n$ for all $n$ .

3. Exact Realization by Selective SSMs

The paper proves that the theoretical finite-state controllers described above are not just abstract constructs but are exactly realizable by a specific neural architecture.

Architecture: A one-layer finite-precision selective affine SSM with:
- Binary one-hot hidden states.
- Transition matrices with entries in $\{0, 1\}$ .
- Zero biases.
- Selectivity: The transition matrix $A_\omega$ depends on the current observation token $\omega$ .
Significance of Selectivity: The authors emphasize that selectivity is the critical architectural ingredient. A fixed linear time-invariant recurrence (non-selective) cannot implement arbitrary finite control in this setting.
Dimension: The hidden dimension required is $d = O(|Q| \cdot |\Gamma|)$ , which is linear in the size of the simulated machine's state space when using one-hot encoding.

4. Exact Resource Accounting (Supplementary Results)

The supplementary material refines the resource bounds:

Logarithmic Simulation: By hard-coding the machine description into the fixed readout and using the tape as external memory, $O(\log B)$ recurrent bits suffice to simulate any $B$ -state Turing machine. This improves the dimension from $O(|Q|)$ to $O(\log |Q|)$ .
Impossibility of Direct Realization: Without external memory, exactly realizing an arbitrary $B$ -state transition map in a single affine recurrent update requires a total recurrent dimension of exactly $B-1$ . This confirms that the logarithmic gain is strictly dependent on offloading the state to the external tape.

Significance and Claims

The paper claims to provide a precise resource-accounting picture of tool-augmented recurrent computation. Its primary significance lies in establishing a sharp dichotomy:

Finite-state tools are computationally "free" in terms of expressivity class (they remain regular) but incur a small, linear memory cost.
Unbounded tape tools provide a massive leap in expressivity (to Turing completeness) with a minimal, logarithmic internal memory cost, provided the controller architecture supports selectivity.

The work resolves the question of when tool use increases power: it is governed entirely by the state space and interface of the tool, not the controller itself. The results are exact constructions and unconditional lower bounds, relying on no training, approximation, or probabilistic arguments. The paper concludes that the "selective" nature of modern SSMs (where transitions depend on inputs) is the specific mechanism that enables these models to act as exact finite controllers when paired with external memory, bridging the gap between finite-precision models and Turing-complete computation.