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

Jul 16, 2026

Upload by Oliver

Modern sequence models increasingly act as agents that interleave token generation with calls to external tools. The work provides an exact, architecture-level account of when tool access increases computational expressivity. Fixed finite-precision recurrent models are formalized as deterministic finite-state controllers interacting with an oracle via a finite command/observation interface. A sharp dichotomy is proved: finite-state tools add essentially nothing, while a minimal unbounded tape tool yields Turing completeness.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages24

Reading Time1 h 0 min

AccessFree to download

Introduction

Our model

Contributions

Exact expressivity dichotomy

Finite-state tools

Unbounded tape tools

Exact realization with selective SSM controllers

Selectivity and controller construction

arXiv :2607 .06 155v 1 [ cs .FL] 7 Jul 2026 When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models? Nikola Zubi´c [zubic@ifi.uzh.ch](zubic@ifi.uzh.ch) Robotics and Perception Group, University of Zurich Qian Li [liqian.ict@gmail.com](liqian.ict@gmail.com) Shenzhen International Center for Industrial and Applied Mathematics, Shenzhen Research Institute of Big Data Yuyi Wang [yuyiwang920@gmail.com](yuyiwang920@gmail.com) Tengen Intelligence Institute, CRRC Zhuzhou Institute Davide Scaramuzza [sdavide@ifi.uzh.ch](sdavide@ifi.uzh.ch) Robotics and Perception Group, University of Zurich Abstract 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 log2 |M|+O(1) additional bits, so the augmented system remains finite-state. Second, a single minimal infinite-state tool (a tape supporting only local read/write/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 (EQn requires 2n 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 (O(log B) recurrent bits suffice to simulate any B-state Turing machine), and prove a matching impossibility result: without external memory, directly realizing an arbitrary B-state transition map in one exact affine recurrent update requires dimension exactly B − 1, for any number of layers. Together, these results give a precise resource-accounting picture of tool-augmented recurrent computation. Keywords: expressivity; state-space models; tool use; oracle machines; Turing completeness; finite precision; recurrent models; computational complexity © 2026 N. Zubi´c, Q. Li, Y. Wang & D. Scaramuzza. Zubi´c Li Wang Scaramuzza 1. Introduction Sequence models are no longer used only as sequence-to-sequence maps: they are deployed as agents that interleave output generation with calls to external tools such as calculators, code interpreters, retrieval systems, and scratchpads (Schick et al. , 2023; Yao et al. , 2023; Nye et al. , 2021) . This raises a basic theoretical question: Which tools increase the computational expressivity of a fixed finite-precision sequence model, by how much, and at what internal memory cost? The starting point is that any fixed finite-precision recurrent model is, from the standpoint of expressivity, a finite-state machine: a model with B bits of internal state has at most 2B configurations, and hence, without external interaction, recognizes only regular languages (Weiss et al. , 2018; Merrill, 2019; Zubic et al. , 2025) . This covers, in particular, finite-precision structured state-space models (SSMs) (Gu et al. , 2022; Gu and Dao, 2024), whose formal-language limitations have been analyzed in detail (Merrill et al. , 2024; Sarrofet al. , 2024; Zubic et al. , 2025; Zu

FAQs

What question does the paper address about tool use in sequence models?

It asks which tools increase the computational expressivity of a fixed finite-precision sequence model, how much they increase it, and what internal memory cost is required.

Why do finite-state tools add essentially nothing to expressivity?

A finite-state bounded-interface oracle can be internalized by simulating the product state, keeping the augmented system finite-state with only log2|M|+O(1) extra bits.

What kind of tool makes the system Turing complete?

A minimal infinite-state tape tool that supports local read/write/move commands enables a controller with O(log|Q|+log|Γ|) bits of memory to simulate any single-tape Turing machine.

Jul 16, 2026

Upload by Oliver