REVIEW 1 major objections 5 minor 21 references
When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?
T0 review · 1 major / 5 minor · reviewed 2026-07-08 · glm-5.2
Pith's one-line read Tape tool makes finite-state SSMs Turing complete
desk verdict Solid, correct paper giving a clean dichotomy for tool-augmented recurrent models. Proofs check out. The main novelty is the framing and exact resource accounting, not the constructions themselves, which are mostly standard automata theory. The lower bound (Thm 23) is the most original piece. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
A deterministic finite-state controller interacting with a tape oracle through local read/write/move commands, realized exactly by a one-layer selective affine SSM with one-hot binary hidden states and {0,1} transition matrices.
What would settle it
If a fixed (non-selective) linear recurrent model with one common transition matrix could be shown to simulate arbitrary Turing machines with tape access, the claim that selectivity is essential would be falsified.
Extended reading notes
Core claim
The paper's core discovery is that the expressivity boundary for tool-augmented finite-precision recurrent models is determined entirely by whether the tool has bounded or unbounded state. Finite-state tools are internalizable at logarithmic cost and leave the system finite-state; one unbounded tape tool yields Turing completeness with logarithmic internal memory. This boundary is realized exactly in a one-layer selective affine SSM architecture, where input-dependent (selective) transition matrices with binary entries and zero biases suffice to implement arbitrary finite control. The matching impossibility result — that direct realization of a B-state transition map without external memory,
Load-bearing premise
The exact realization by a selective affine SSM requires that the transition matrix can be selected based on the current observation token, and the logarithmic improvement in the appendix additionally relies on the conventions that the tape is free external memory and that fixed parameters and readout tables are not charged to the recurrent-memory budget.
Editorial extensions
If this is right
- If the paper's model is right, the practical question of whether a tool-augmented language model can exceed regular-language expressivity reduces to a single architectural test: does the tool maintain unbounded state?
- The exact SSM construction shows that input-dependent transition matrices are the minimal architectural feature enabling Turing-complete behavior — a fixed transition matrix cannot realize arbitrary finite control, which constrains the design of SSM architectures intended for tool use.
- The exponential EQ_n separation provides a concrete benchmark: any finite-precision recurrent model claiming tool-augmented expressivity should be testable on equality-checking tasks where the gap between 2^n and constant is observable at moderate n.
- The dichotomy between the logarithmic oracle-assisted bound and the linear direct-realization bound quantifies exactly what external persistent memory and machine-specific readout parameters buy, giving a precise resource tradeoff for system designers.
Reading between the lines
- The sharpness of the dichotomy suggests that intermediate tools — those with unbounded but structured state (e.g., a counter, a stack) — should yield intermediate expressivity classes between regular and recursively enumerable, potentially mapping onto known levels of the Chomsky hierarchy. The paper's framework could likely formalize this.
- If selectivity is the key architectural ingredient, one could test whether empirically trained selective SSMs (like Mamba) develop input-dependent transition patterns that resemble the one-hot finite-control structure the paper constructs, by inspecting learned matrices on tool-use tasks.
- The resource-accounting conventions that distinguish the logarithmic from the linear bound suggest a design principle: for practical systems, hard-coding machine descriptions in readout parameters and using the tape as external memory may be far more parameter-efficient than attempting to encode transition logic in recurrent state alone.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies when external tool access increases the expressive power of finite-precision recurrent models. The authors model any such model as a deterministic finite-state controller interacting with an oracle through a finite interface. They prove a sharp dichotomy: (1) finite-state bounded-interface oracles can be internalized at a cost of only log|M| + O(1) bits (Proposition 4), leaving the system finite-state; (2) a single tape oracle with local read/write/move commands yields Turing completeness with O(log|Q| + log|Γ|) bits of controller memory (Theorem 7). They further show this construction is realized exactly by a one-layer selective affine SSM with binary one-hot hidden states, {0,1} transition matrices, and zero biases (Theorem 13). A concrete exponential separation is given via EQ_n (Theorem 9). The supplementary material provides a fully explicit constant (C_0 = 9), a logarithmic oracle-assisted universal simulation (Theorem 19), and a matching lower bound showing that without external memory, exact one-step realization of an arbitrary B-state transition map requires dimension exactly B-1 (Theorem 23).
Significance. The paper provides a clean, exact, and constructive characterization of tool-augmented recurrent computation. The dichotomy is well-motivated and the results are fully formal. Particular strengths include: (a) the constructive proofs with explicit constants (e.g., C_0 = 9 in Appendix A); (b) the exact SSM realization with zero biases and binary transition matrices (Lemma 12), which makes the positive result architecture-specific rather than abstract; (c) the matching lower bound (Theorem 23) that closes the gap between the logarithmic oracle-assisted simulation and the linear direct-realization requirement, with a transparent explanation of why the two are compatible (Remark 24). The resource conventions in Appendix B are explicitly stated, which is commendable. The paper is largely self-contained, citing Neary and Woods (2009) only for the existence of a fixed universal Turing machine.
major comments (1)
- Remark 14 states informally that a fixed linear time-invariant (non-selective) SSM 'is not automatically able to implement arbitrary finite-state control.' This is a meaningful claim that is naturally suggested by the contrast between the selective construction (Theorem 13) and the lower bound (Theorem 23), but it is not formally proved in the manuscript. The paper is careful to say 'is not claimed' and 'is not automatically able,' so this does not affect any stated theorem. However, since selectivity is identified as 'the architectural ingredient that suffices for exact finite control' (Section 9), a brief formal statement of what non-selective SSMs with tape access cannot do—or an explicit acknowledgment that this is left as an open question—would strengthen the narrative. This is a minor gap in framing rather than a load-bearing issue for any theorem.
minor comments (5)
- Section 8.2: The action alphabet Act includes 'stay' as a command, but the tape oracle in Section 5 (Definition 6) does not list 'stay' among its commands. The appendix (Appendix A) does include 'stay.' A brief note reconciling these definitions, or a forward reference, would improve clarity.
- Theorem 19, Eqs. (1)-(3): The notation D_ω for the one-hot transition matrices of the scanner/universal controller is introduced without explicit definition of the subscript set. It would help to state that D_ω is defined for ω ∈ {ok, ⊔, 0, 1} and that D_0, D_1 apply when the universal controller reads tape symbols 0 or 1 during its own operation.
- Table 1: The row 'none, EQ_n ≥ 2^n states —' lists the tool as 'none' but does not specify controller memory. For consistency with other rows, it could note '≥ n bits' or '≥ 2^n states.'
- Lemma 18: The encoding length bound |⟨M⟩| ≤ cB log₂(B+1) uses a constant c whose value is not made explicit. While this is standard for an O-notation result, the paper's emphasis on making constants explicit (cf. C_0 = 9 in Appendix A) suggests that providing a value or an explicit bound on c would be consistent with the paper's own standards.
- The paper uses both 'selective affine SSM' and 'selective affine state-space controller' in different places. Standardizing the terminology would improve readability.
Simulated Author's Rebuttal
We thank the referee for a careful and positive reading. The report identifies one minor gap in framing: Remark 14 informally notes that non-selective (fixed LTI) SSMs are not automatically able to implement arbitrary finite-state control, but this claim is not formally proved. We agree this is a framing gap, not a load-bearing issue for any theorem, and will address it in revision.
read point-by-point responses
-
Referee: Remark 14 states informally that a fixed linear time-invariant (non-selective) SSM 'is not automatically able to implement arbitrary finite-state control.' This is a meaningful claim... but it is not formally proved in the manuscript. A brief formal statement of what non-selective SSMs with tape access cannot do—or an explicit acknowledgment that this is left as an open question—would strengthen the narrative.
Authors: We agree with the referee that Remark 14 makes an informal claim that deserves sharper framing. To be precise about what we can and cannot currently say: (1) What we have proved: Theorem 23 shows that without external memory, exactly realizing an arbitrary B-state transition map in one affine recurrent update requires dimension B-1, for any number of triangular selective-affine layers. Since selectivity is a generalization of the non-selective (fixed LTI) case, this lower bound applies a fortiori to non-selective SSMs. (2) What we have not proved: a formal impossibility result for non-selective SSMs *with* tape access. The tape-access setting introduces oracle interactions that complicate the direct-realization argument, and we have not extended the lower-bound machinery to that setting. We will revise Remark 14 to state this distinction explicitly: the non-selective case is constrained by Theorem 23 in the no-external-memory regime, but whether non-selective SSMs with tape access can or cannot achieve Turing completeness is left as an open question. This is an honest acknowledgment of the boundary of our results and does not affect any stated theorem. revision: yes
Circularity Check
No circularity found. All main results are proved constructively from first principles.
full rationale
The paper's derivation chain is self-contained and non-circular. Proposition 4 (product-state simulation) is a standard automata-theory construction with a clean induction proof. Theorem 7 (Turing completeness via tape) builds a controller that faithfully simulates a TM through read/write/move commands, with an explicit invariant. Theorem 9 (EQ_n lower bound) uses a standard pigeonhole argument for part (i) and instantiates Theorem 7 for part (ii). Lemma 12 (one-hot SSM realization) defines A_ω columnwise from the transition function δ and proves by induction that the SSM reproduces the controller—this is a genuine constructive realization, not a definitional identity. Theorem 13 composes Theorem 7 and Lemma 12 straightforwardly. Theorem 19 (logarithmic simulation) cites Neary and Woods (2009) for the existence of a small universal Turing machine—an external, independent result—and the construction hard-codes the machine description in the readout table, with resource conventions transparently stated in Remark 20. Theorem 23 (lower bound, D_L(B) = B−1) uses a specific automaton with only trivial congruences and a nilpotent orbit argument, proved from scratch. Self-citations (Zubic et al. 2025, 2026) appear only in the related-work section for background context and are not load-bearing for any theorem. No fitted parameters, no definitional reductions, no self-citation chains.
Assumptions & free parameters
assumptions (5)
- standard math Any fixed finite-precision recurrent model with B bits of state induces a finite-state controller with at most 2^B states (Remark 2).
- standard math Deterministic single-tape Turing machines in output-normal form can compute any partial computable string function (Section 6).
- standard math Existence of a fixed universal one-tape Turing machine with three tape symbols (Lemma 18, citing Neary and Woods 2009).
- domain assumption The tape oracle provides free external persistent memory; fixed parameters and readout tables are not charged to the recurrent-memory budget (Remark 20).
- domain assumption The selective affine SSM model allows transition matrices to depend on the current observation token (Definition 11).
invented entities (2)
-
Tape oracle (O_tape)
independent evidence
-
Observation-driven finite-state controller (Definition 10)
independent evidence
Cite this review
Pith. "Pith review of When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?." pith.science (2026). https://pith.science/paper/CJGUG6R6
@misc{pith2026260706155,
author = {Pith},
title = {Pith review of: When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?},
year = {2026},
howpublished = {\url{https://pith.science/paper/CJGUG6R6}},
note = {Machine review of arXiv:2607.06155}
}
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 $\Gamma$, a controller with $O(\log |Q| + \log |\Gamma|)$ 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.
Reference graph
Works this paper leans on
-
[1]
International Conference on Learning Representations , volume=
Limits of deep learning: Sequence modeling through the lens of complexity theory , author=. International Conference on Learning Representations , volume=
-
[2]
On the Expressive Power and Limitations of Multi-Layer SSMs
On the Expressive Power and Limitations of Multi-Layer SSMs , author=. arXiv preprint arXiv:2604.14501 , year=
-
[3]
Fundamenta Informaticae , volume=
Four small universal Turing machines , author=. Fundamenta Informaticae , volume=. 2009 , publisher=
work page 2009
-
[4]
International Conference on Learning Representations (ICLR) , year=
Efficiently modeling long sequences with structured state spaces , author=. International Conference on Learning Representations (ICLR) , year=
-
[5]
First Conference on Language Modeling (COLM) , year=
Mamba: Linear-time sequence modeling with selective state spaces , author=. First Conference on Language Modeling (COLM) , year=
-
[6]
International Conference on Machine Learning (ICML) , year=
The illusion of state in state-space models , author=. International Conference on Machine Learning (ICML) , year=
-
[7]
Advances in Neural Information Processing Systems , volume=
The expressive capacity of state space models: A formal language perspective , author=. Advances in Neural Information Processing Systems , volume=
-
[8]
International Conference on Learning Representations , volume=
Unlocking state-tracking in linear rnns through negative eigenvalues , author=. International Conference on Learning Representations , volume=
Show all 21 references
-
[9]
Proceedings of the fifth annual workshop on Computational learning theory , pages=
On the computational power of neural nets , author=. Proceedings of the fifth annual workshop on Computational learning theory , pages=
-
[10]
Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers) , pages=
On the practical computational power of finite precision RNNs for language recognition , author=. Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers) , pages=
-
[11]
Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges , pages=
Sequential neural networks as automata , author=. Proceedings of the Workshop on Deep Learning and Formal Languages: Building Bridges , pages=
-
[12]
Transactions of the Association for Computational Linguistics , volume=
The parallelism tradeoff: Limitations of log-precision transformers , author=. Transactions of the Association for Computational Linguistics , volume=
-
[13]
International Conference on Learning Representations , volume=
The expressive power of transformers with chain of thought , author=. International Conference on Learning Representations , volume=
-
[14]
Journal of Machine Learning Research , volume=
Attention is turing-complete , author=. Journal of Machine Learning Research , volume=
-
[15]
International Conference on Learning Representations (ICLR) , year=
Neural networks and the chomsky hierarchy , author=. International Conference on Learning Representations (ICLR) , year=
-
[16]
Advances in neural information processing systems , volume=
Toolformer: Language models can teach themselves to use tools , author=. Advances in neural information processing systems , volume=
-
[17]
Yao, Shunyu and Zhao, Jeffrey and Yu, Dian and Du, Nan and Shafran, Izhak and Narasimhan, Karthik and Cao, Yuan , booktitle =
-
[18]
ICLR 2022 Workshop DL4C , year=
Show your work: Scratchpads for intermediate computation with language models , author=. ICLR 2022 Workshop DL4C , year=
2022
-
[19]
First conference on language modeling , year=
On limitations of the transformer architecture , author=. First conference on language modeling , year=
-
[20]
Advances in neural information processing systems , volume=
Faith and fate: Limits of transformers on compositionality , author=. Advances in neural information processing systems , volume=
-
[21]
Advances in neural information processing systems , volume=
Chain-of-thought prompting elicits reasoning in large language models , author=. Advances in neural information processing systems , volume=
Reviewed July 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.