{"ID":6023526,"CreatedAt":"2026-07-08T01:00:23.257252134Z","UpdatedAt":"2026-07-10T11:13:51.816948337Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.06155","arxiv_id":"2607.06155","title":"When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?","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 $\\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.","short_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 s...","url_abs":"https://arxiv.org/abs/2607.06155","url_pdf":"https://arxiv.org/pdf/2607.06155v1","authors":"[\"Nikola Zubić\",\"Qian Li\",\"Yuyi Wang\",\"Davide Scaramuzza\"]","published":"2026-07-07T11:32:56Z","proceeding":"cs.FL","tasks":"[\"cs.FL\",\"cs.CC\",\"cs.CL\"]","methods":"[]","has_code":false}