For longer-horizon tasks, we often think about using a long-context model. But harnesses also matter! In fact, they are inherently different in computational power.

Our ICML paper “Recursive Models for Long-Horizon Reasoning” introduces a simple recursive harness, and studies how different harnesses affect a base model’s expressiveness under resource constraints.

1/n

Paper: https://arxiv.org/abs/2603.02112 Code: https://github.com/chr26195/RecursiveModel…

---

Recursive Models for Long-Horizon Reasoning

Source: https://arxiv.org/html/2603.02112

Abstract

Modern language models reason within bounded context, an inherent constraint that poses a fundamental barrier to long-horizon reasoning. We identify recursion as a core principle for overcoming this barrier, and propose recursive models as a minimal realization, where the model can recursively invoke itself to solve subtasks in isolated contexts. We prove that any computable problem admits a recursive decomposition of reasoning in which each subtask requires only exponentially smaller active context than standard autoregressive models; this strictly surpasses any context management approach confined to a single sequence, such as summarization. We further generalize our framework to modern agentic systems with arbitrary context processing and control flows, and prove that recursive models can achieve optimal power within this broader class. Experimentally, we test two settings: fine-tuning a pretrained base model for recursive SAT solving, and training a small model from scratch on Go traces generated by exact game-tree search. Both show improved long-horizon accuracy with small active contexts.

Machine Learning, ICML

1Introduction

(a)Standard Autoregressive Model.The model generates tokens sequentially, appending each to the current sequence until the context limit is reached. (b)Single-Context Model.The entire generation process operates within a single sequence. As a representative example, summarization periodically compresses past reasoning into a compact summary and discards the original tokens. (c)Recursive Model.Unlike the previous two approaches, computation spans multiple isolated contexts. The model delegates subtasks viacall, each solved in a fresh context;returnpasses back only the result, discarding intermediate reasoning. This enables unbounded recursion depth without growing any single context.

Figure 1:Overview of different context management strategies.Modern language models exhibit remarkable general problem solving power(Radford et al.,2018,2019; Brown et al.,2020; OpenAI et al.,2023). Through extended thinking(Wei et al.,2022; OpenAI,2024; DeepSeek-AI et al.,2025)and agentic systems(Yao et al.,2023; Shinn et al.,2023; Park et al.,2023), they can handle increasingly complex tasks across diverse domains. Nevertheless, these systems are subject to a physical constraint: at every step, the model can only attend to bounded-sized context window, strictly limiting what can be computed in a single forward pass.

This has driven growing interest in effective context management. For instance, summarization compresses lengthy reasoning traces into compact states, discarding no longer needed history to free up space(Yang et al.,2025a; Yu et al.,2025; Zhou et al.,2025; Yan et al.,2025); memory-augmented approaches write and retrieve relevant information in external storage(Packer et al.,2024; Chhikara et al.,2025; Suzgun et al.,2025; Xu et al.,2025); and in agentic systems, subtasks are distributed across agents, each operating in its own context while collaborating toward a shared goal(Hong et al.,2024; Wu et al.,2023; Li et al.,2023).

Yet questions remain: how do these different systems formally compare in their reasoning power? What core mechanisms, as scaffolding that wraps around the base generator, can enable models to handle long-horizon tasks that are otherwise impossible because of context constraints? And are these mechanisms optimal? Despite the importance of these questions, existing work lacks a formalization for these questions to be answered systematically. Notable related works areYang et al. (2025a,b), which, however, focus on summarization-based context management and self-correction in diffusion language models respectively.

In this work, we identify recursion as a core principle for overcoming context constraints, and a form of computational power naturally enabled by modern agentic systems. In a broad sense, recursion refers to the application of a finite, static set of rules to a target problem, that dynamically produces a potentially infinite depth of behaviors that, though contextually isolated from each other, contribute to the final solution.

We propose the simplest realization of this principle, which we call recursive model. It consists of a single base LLM as the generator, equipped with two minimal tools,callandreturn. As illustrated inFigure˜1(c), the model can invoke itself:callcreates an isolated context and the model solves the subtask there independently; upon completion,returndiscards the intermediate reasoning and passes only the final answer back to the parent context. Since each invoked model can itself invoke further calls, this enables a deep context stack while keeping each individual context bounded by the maximal context length. Similar ideas have been explored in earlier and concurrent work(Lee & Kim,2023; Prasad et al.,2024; Schroeder et al.,2025; Pan et al.,2025; Zhang et al.,2025c; Sun et al.,2025; Zhang et al.,2025a); see a comprehensive discussion inAppendix˜A.

One important observation is that the recursive model naturally induces a separation between local and global space: the generator only needs to attend to the active context, while inactive contexts in the context stack can be offloaded to external storage and restored upon return. While this improves space efficiency, it seems to impose a strong requirement that problems must admit modular decompositions. Do general computational problems possess such structure? We show the answer is affirmative: any computable problem inherently admits a recursive decomposition, and furthermore, by doing so, the required context can be reduced exponentially. Specifically, we prove that with local spaceS​(n)S(n), recursive models can solve any problem requiring up toexp⁡(𝒪​(S​(n)))\exp(\mathcal{O}(S(n)))computation time. In comparison, standard autoregressive models would require context lengthexp⁡(𝒪​(S​(n)))\exp(\mathcal{O}(S(n)))to solve the same problems, which is an exponential gap.

Recursion, however, is not the only approach for context management. Consider summarization (Figure˜1(b)), which periodically compresses the context and discards old history to keep the context window bounded. Unlike recursion, summarization and indeed most existing strategies keep the entire generation process within a single sequence. We call these single-context models. Prior work(Yang et al.,2025a)shows that with context lengthS​(n)S(n), summarization can solve all problems requiringS​(n)S(n)space. We prove that this is in fact optimal: no single-context model, regardless of its context management strategy, can surpass summarization, which is, however, still strictly less powerful than recursion. Indeed, we show that even constant-depth recursion (i.e., depth 1) suffices to match the optimum of all single-context models. Moreover, deeper recursion breaks through this ceiling, solving problems beyond what any single-context approach can reach. This separates the power of recursive models from those shallow counterparts(Sun et al.,2025; Zhang et al.,2025a).

Modern agentic systems are unique in that they are no longer confined to a single context: they can dynamically spawn contextually isolated sub-agents to solve specialized subtasks independently, and the responses are integrated back, processed, and used to determine the system’s next behavior. This unique feature enables recursion in broader use cases. While not all agentic systems possess this capability, we formalize a powerful family called recursive agentic systems, which equip agentic systems with scaffoldings that create a recursive control loop. The recursive model is the minimal realization of this family. We show that any agentic system that is recursive can reach the same power as recursive models, enabling them to break through context constraints far beyond standard approaches. Yet, none can surpass recursive models, suggesting that the recursive model, despite its simplicity, is already optimally powerful within this family.

Experimentally, we evaluate recursive models in two settings. On SAT, we fine-tune a pretrained base model on recursive backtracking traces and compare against strong prompted LLM baselines. On4×44\times 4Go game-tree evaluation, we train a small decoder-only model from scratch on traces generated by an exact solver, giving a controlled recursive-search task whose generalized form isEXPTIME-complete and is therefore suitable for testing exponential-time recursive reasoning. On Go, recursive call/return traces let the model evaluate longer game-tree searches without placing the whole proof in one context. This outperforms CoT and the single-context baseline and gives stronger length-OOD generalization.

Algorithm 1Autoregressive Generator,fcotf^{\mathrm{cot}}0:Input sequence

𝐱∈Σ∗\mathbf{x}\in\Sigma^{*}, next-token generator

π:Σ∗→Σ\pi:\Sigma^{*}\to\Sigma, stopping condition

𝗌𝗍𝗈𝗉:Σ∗→{0,1}\mathsf{stop}:\Sigma^{*}\to\{0,1\}.

1:while

¬𝗌𝗍𝗈𝗉​(𝐱)\neg\mathsf{stop}(\mathbf{x})do

2:Generate

y←π​(𝐱)y\leftarrow\pi(\mathbf{x}) 3:Append

𝐱←𝐱∥y\mathbf{x}\leftarrow\mathbf{x}\mathbin{\|}y 4:return

𝐱\mathbf{x}

Algorithm 2Recursive Model,frmf^{\mathrm{rm}}0:

𝐱∈Σ∗\mathbf{x}\in\Sigma^{*}; sequence generator

f:Σ∗⇀Σ∗f:\Sigma^{*}\rightharpoonup\Sigma^{*}whose defined outputs end with a call or return string.

1:while true:

2:

𝐲←f​(𝐱)\mathbf{y}\leftarrow f(\mathbf{x}) 3:if

𝐲=𝐲′∥⟨return⟩𝐚⟨/return⟩\mathbf{y}=\mathbf{y}^{\prime}\mathbin{\|}\langle\texttt{return}\rangle\mathbf{a}\langle/\texttt{return}\rangle:return

𝐚\mathbf{a} 4:if

𝐲=𝐲′∥⟨call⟩𝐪⟨/call⟩\mathbf{y}=\mathbf{y}^{\prime}\mathbin{\|}\langle\texttt{call}\rangle\mathbf{q}\langle/\texttt{call}\rangle:

𝐱←𝐲′∥frm​(𝐪)\mathbf{x}\leftarrow\mathbf{y}^{\prime}\mathbin{\|}f^{\mathrm{rm}}(\mathbf{q})

2Recursive Models

This section defines the recursive model. The construction takes a partial sequence generatorf:Σ∗⇀Σ∗f:\Sigma^{*}\rightharpoonup\Sigma^{*}, which maps a prompt, or more generally a context, to a generated sequence. Our default choice is the CoT sequence generatorfcotf^{\mathrm{cot}}, obtained by autoregressive rollout from a next-token generator.

Autoregressive Generator.

Letπ:Σ∗→Σ\pi:\Sigma^{*}\to\Sigmabe a next-token generator and let𝗌𝗍𝗈𝗉:Σ∗→{0,1}\mathsf{stop}:\Sigma^{*}\to\{0,1\}be a stopping condition. Algorithm1defines the partial sequence generatorfcot:Σ∗⇀Σ∗f^{\mathrm{cot}}:\Sigma^{*}\rightharpoonup\Sigma^{*}. Starting from an input sequence𝐱\mathbf{x}, the rollout repeatedly appends the tokenπ​(𝐱)\pi(\mathbf{x})until𝗌𝗍𝗈𝗉​(𝐱)=1\mathsf{stop}(\mathbf{x})=1, then returns the final sequence. If𝗌𝗍𝗈𝗉\mathsf{stop}never holds,fcot​(𝐱)f^{\mathrm{cot}}(\mathbf{x})is undefined. We write𝐱∥𝐳\mathbf{x}\mathbin{\|}\mathbf{z}for sequence concatenation.

Recursive Model.

Fix a partial sequence generatorf:Σ∗⇀Σ∗f:\Sigma^{*}\rightharpoonup\Sigma^{*}; by default,f=fcotf=f^{\mathrm{cot}}. We define the recursive model induced byffas a functionfrm:Σ∗⇀Σ∗f^{\mathrm{rm}}:\Sigma^{*}\rightharpoonup\Sigma^{*}. We suppress the dependence onffin the notation. Its input𝐱\mathbf{x}is the full root prompt, and its output, when defined, is the answer returned by the root context. Execution starts from the root stack𝐒0=[𝐱]\mathbf{S}_{0}=[\mathbf{x}].

Fort=0,1,…t=0,1,\ldots,𝐒t\mathbf{S}_{t}denotes the stack afterttstack updates; each update happens after one complete call toff, not after one generated token in Algorithm1. Each stack𝐒t∈(Σ∗)+\mathbf{S}_{t}\in(\Sigma^{*})^{+}is a non-empty list of token sequences. Only the top sequence is active: it is the full input passed toffat stack updatett. The lower sequences𝐒t[:−1]\mathbf{S}_{t}[:-1]are suspended parent contexts that are not visible toffuntil control returns to them. For a stack𝐒\mathbf{S}and sequences𝐬1,…,𝐬k\mathbf{s}_{1},\ldots,\mathbf{s}_{k},𝖯𝗎𝗌𝗁​(𝐒;𝐬1,…,𝐬k)\mathsf{Push}(\mathbf{S};\mathbf{s}_{1},\ldots,\mathbf{s}_{k})appends them to𝐒\mathbf{S}in order.

The recursive model uses four reserved delimiter tokens⟨call⟩,⟨/call⟩,⟨return⟩,⟨/return⟩∈Σ\langle\texttt{call}\rangle,\langle/\texttt{call}\rangle,\langle\texttt{return}\rangle,\langle/\texttt{return}\rangle\in\Sigma. We write⟨call⟩𝐪⟨/call⟩\langle\texttt{call}\rangle\mathbf{q}\langle/\texttt{call}\rangleand⟨return⟩𝐚⟨/return⟩\langle\texttt{return}\rangle\mathbf{a}\langle/\texttt{return}\ranglefor the delimited call and return strings. When the default choicef=fcotf=f^{\mathrm{cot}}is used, the stopping condition in Algorithm1is chosen so thatfcotf^{\mathrm{cot}}returns only when the current sequence ends with one of these strings.

A call pauses the current context and starts a new child context for the subproblem. A non-root return removes the child context and appends only its answer to the parent; the child’s intermediate tokens are not copied back. Formally, at stack updatett, runffon the active context and let𝐲t:=f​(𝐒t​[−1])\mathbf{y}_{t}:=f(\mathbf{S}_{t}[-1]). The generator first produces the full sequence𝐲t\mathbf{y}_{t}; only then do we parse its final call or return. We represent this intermediate state by replacing the old stack top with𝐲t\mathbf{y}_{t}, and then apply the stack update rule:

𝐒~t:=𝖯𝗎𝗌𝗁(𝐒t[:−1];𝐲t),𝐒t+1=𝖲𝗍𝖾𝗉(𝐒~t).\displaystyle\widetilde{\mathbf{S}}_{t}:=\mathsf{Push}(\mathbf{S}_{t}[:-1];\mathbf{y}_{t}),\qquad\mathbf{S}_{t+1}=\mathsf{Step}(\widetilde{\mathbf{S}}_{t}).(1)Thus𝐒~t\widetilde{\mathbf{S}}_{t}is the stack after the generator output is produced, while𝐒t+1\mathbf{S}_{t+1}is the stored stack after the call or return is processed. The map𝖲𝗍𝖾𝗉\mathsf{Step}is defined on a transient stack𝐒~\widetilde{\mathbf{S}}by two cases. Write𝐲:=𝐒~​[−1]\mathbf{y}:=\widetilde{\mathbf{S}}[-1]for its top sequence.

Call:​𝖲𝗍𝖾𝗉​(𝐒~)\displaystyle\text{Call: }\mathsf{Step}(\widetilde{\mathbf{S}})=𝖯𝗎𝗌𝗁(𝐒~[:−1];𝐲′,𝐪)\displaystyle=\mathsf{Push}(\widetilde{\mathbf{S}}[:-1];\mathbf{y}^{\prime},\,\mathbf{q})(2)if𝐲=𝐲′∥⟨call⟩𝐪⟨/call⟩;\displaystyle\quad\text{if }\mathbf{y}=\mathbf{y}^{\prime}\mathbin{\|}\langle\texttt{call}\rangle\mathbf{q}\langle/\texttt{call}\rangle;Return:​𝖲𝗍𝖾𝗉​(𝐒~)\displaystyle\text{Return: }\mathsf{Step}(\widetilde{\mathbf{S}})=𝖯𝗎𝗌𝗁(𝐒~[:−2];𝐒~[−2]∥𝐚)\displaystyle=\mathsf{Push}(\widetilde{\mathbf{S}}[:-2];\widetilde{\mathbf{S}}[-2]\mathbin{\|}\mathbf{a})if𝐲=𝐲′∥⟨return⟩𝐚⟨/return⟩\displaystyle\quad\text{if }\mathbf{y}=\mathbf{y}^{\prime}\mathbin{\|}\langle\texttt{return}\rangle\mathbf{a}\langle/\texttt{return}\rangleand​|𝐒~|>1.\displaystyle\quad\text{and }|\widetilde{\mathbf{S}}|>1.A root return is not a stack update. If|𝐒~t|=1|\widetilde{\mathbf{S}}_{t}|=1and𝐒~t[−1]=𝐲′∥⟨return⟩𝐚⟨/return⟩\widetilde{\mathbf{S}}_{t}[-1]=\mathbf{y}^{\prime}\mathbin{\|}\langle\texttt{return}\rangle\mathbf{a}\langle/\texttt{return}\rangle, the computation terminates and returns𝐚\mathbf{a}. The recursive model is partial: if some call toffis undefined, ifffreturns a sequence that matches neither form above, if a child computation is undefined, or if execution never reaches a root return, thenfrm​(𝐱)f^{\mathrm{rm}}(\mathbf{x})is undefined.

Algorithm2gives an equivalent recursive view of the same process, showing only the active context𝐱\mathbf{x}. In the call case,𝐱←𝐲′∥frm​(𝐪)\mathbf{x}\leftarrow\mathbf{y}^{\prime}\mathbin{\|}f^{\mathrm{rm}}(\mathbf{q})means: pause the parent after𝐲′\mathbf{y}^{\prime}, solve the child prompt𝐪\mathbf{q}using the same sequence generatorff, append the child’s returned answer, and continue in the parent.

In the experiments, we run this model with a finite iteration budget;§\mathsection˜B.3gives the exact procedure.

2.1Variants and Extensions

The basic recursive model above is our default. We will also use two variants that change only what information is visible in a context, while leaving the meaning of call and return unchanged.

Variant 1: Prompt Prefixing.

Some constructions need every child call to see the original problem instance. Let𝐱0\mathbf{x}_{0}denote the root prompt. Instead of copying𝐱0\mathbf{x}_{0}into every generated subproblem, we expose it as a fixed prefix whenever the active context is non-root:

𝐱0∥𝐲t=f​(𝐱0∥𝐒t​[−1]),when​|𝐒t|>1.\mathbf{x}_{0}\mathbin{\|}\mathbf{y}_{t}=f(\mathbf{x}_{0}\mathbin{\|}\mathbf{S}_{t}[-1]),\quad\text{when }|\mathbf{S}_{t}|>1.(3)Here𝐲t\mathbf{y}_{t}is the generator output after removing the fixed prefix𝐱0\mathbf{x}_{0}; for the default CoT rolloutfcotf^{\mathrm{cot}}, this prefix is always present because rollout only appends tokens to its input. The stack update itself is still the ordinary transition inEquation˜1. Root-level steps do not add this prefix.

Variant 2: Question Preservation.

In the basic call rule, the parent keeps only𝐲′\mathbf{y}^{\prime}while the child receives𝐪\mathbf{q}as its complete prompt. Thus, after the child returns, the parent sees the answer but not the subtask text. To keep the subtask text in the parent as well, replace the call rule by

𝐒t+1=𝖯𝗎𝗌𝗁(𝐒t[:−1];𝐲′∥𝐪,𝐪).\mathbf{S}_{t+1}=\mathsf{Push}(\mathbf{S}_{t}[:-1];\mathbf{y}^{\prime}\mathbin{\|}\mathbf{q},\,\mathbf{q}).(4)This changes only what the parent remembers; the child prompt is still𝐪\mathbf{q}.

Further Extensions.

§\mathsection˜4formalizes a more general model in which the fixed stack-transition rule is replaced by a scaffold. Such a scaffold may parse model outputs, add instructions, call tools or other generators, and decide when to launch a recursive call. We call the resulting systems recursive agentic systems. Unless a variant or extension is explicitly invoked, all results use the basic recursive model above.

3Computational Power of Recursive Models

Recursive calls organize complex tasks as nested subcomputations. The key resource question is simple: the full stack may be large, but the generator sees only the top context at any moment. We therefore measure both the total stack size and the largest active context, and ask how much power is gained by allowing deep recursion rather than forcing all reasoning into one sequence.

3.1Separation of Global and Local Spaces

Unlike the standard generation process where context grows monotonically, recursive models work on a stack of sequences, which gives rise to two natural resource measures:

Definition 1(Global and Local Space).

For a stack𝐒\mathbf{S}, we define theglobal spaceandlocal spacerespectively as:

𝖦𝖲​(𝐒):=∑𝐬∈𝐒|𝐬|,𝖫𝖲​(𝐒):=max𝐬∈𝐒⁡|𝐬|,\mathsf{GS}(\mathbf{S}):=\sum_{\mathbf{s}\in\mathbf{S}}|\mathbf{s}|,\qquad\mathsf{LS}(\mathbf{S}):=\max_{\mathbf{s}\in\mathbf{S}}|\mathbf{s}|,(5)where global space𝖦𝖲\mathsf{GS}refers to the total number of tokens across all sequences, and local space𝖫𝖲\mathsf{LS}refers to the length of the longest sequence.

This resource distinction is practically significant: theglobal spacecorresponds to the total size of the current stack (including suspended and active contexts). Suspended contexts (i.e., all but the stack top) are temporarily inactive and can be stored outside the active attention window as text, token sequences, or KV caches, so storage size and transfer latency are implementation costs rather than part of the local-space measure.

In contrast,local spaceis the maximum length of the active context window throughout next-token generation. Unlike suspended contexts, the active context must fit within the model’s attention window during each generator call, making local space the practical bottleneck.We thus focus our analysis on the reasoning power achievable under strict local space constraints.

Base Transformer Model.

For the complexity results, the next-token generator is a constant-size causal Transformer with average-hard attention, as formalized inAppendix˜D. Autoregressive rollout turns this generator into the CoT sequence function from§\mathsection˜2, and the stack update rule then turns that sequence function into a recursive model.

RM Complexity Class.

We use𝖱𝖬\mathsf{RM}for language classes, andfrmf^{\mathrm{rm}}for an individual recursive model. A fixed recursive model decides a language if, on every input, the root context returns a designated accept or reject symbol. The class𝖱𝖬​(S​(n),D​(n),T​(n))\mathsf{RM}(S(n),D(n),T(n))records what can be decided when the active context length, recursion depth, and total number of generated tokens are bounded byS​(n)S(n),D​(n)D(n), andT​(n)T(n).

Definition 2(Recursive Model Complexity Class).

For functionsS,D,T:ℕ→ℕS,D,T:\mathbb{N}\to\mathbb{N}, the class𝖱𝖬​(S​(n),D​(n),T​(n))\mathsf{RM}(S(n),D(n),T(n))consists of all decision problems solvable by recursive models obtained from constant-size,𝒪​(log⁡S​(n))\mathcal{O}(\log S(n))-precision Transformers as above, such that for all inputs𝐱∈Σn\mathbf{x}\in\Sigma^{n}:

1. 1.Local Space:maxt⁡𝖫𝖲​(𝐒~t)≤S​(n)\max_{t}\mathsf{LS}(\widetilde{\mathbf{S}}_{t})\leq S(n), wherettranges over completed generator calls, including the final root-return call;
2. 2.Recursion Depth:maxt⁡|𝐒t|≤D​(n)\max_{t}|\mathbf{S}_{t}|\leq D(n)(the stack depth is bounded byD​(n)D(n));
3. 3.Total Steps: the total number of generated tokens is at mostT​(n)T(n).

HereS​(n)S(n)bounds the total length of one active context, including the original input or prompt prefix whenever it is visible to that call. When no time constraint is imposed, we write it as𝖱𝖬​(S​(n),D​(n))\mathsf{RM}(S(n),D(n)).

Standard Complexity Classes.

To characterize the expressivity of recursive models, we compare with standard Turing machine complexity classes. We denote by𝖳𝖨𝖬𝖤​(T​(n))\mathsf{TIME}(T(n))and𝖲𝖯𝖠𝖢𝖤​(S​(n))\mathsf{SPACE}(S(n))the classes of problems solvable inT​(n)T(n)time andS​(n)S(n)space, respectively. We write𝖳𝖬​(S​(n),T​(n))\mathsf{TM}(S(n),T(n))for the simultaneous class of languages decided by a deterministic Turing machine that uses𝒪​(S​(n))\mathcal{O}(S(n))space and𝒪​(T​(n))\mathcal{O}(T(n))time on all inputs. (SeeAppendix˜Efor formal definitions.)

3.2Main Result

Now we formally establish the computational power of recursive models with unbounded recursion depth.

Theorem 1(Deep Recursive Models).

For anyS​(n)≥nS(n)\geq n, recursive models can solve any problem in𝖳𝖨𝖬𝖤​(2𝒪​(S​(n)))\mathsf{TIME}(2^{\mathcal{O}(S(n))})under local space constraint𝒪​(S​(n))\mathcal{O}(S(n)):

𝖳𝖨𝖬𝖤​(2𝒪​(S​(n)))⊆𝖱𝖬​(𝒪​(S​(n)),∞,∞).\mathsf{TIME}(2^{\mathcal{O}(S(n))})\subseteq\mathsf{RM}(\mathcal{O}(S(n)),\infty,\infty).(6)

The theorem is about active working context: exponentially long computations can be organized into many small frames. At each step, the generator attends only to the current frame, while suspended frames are stored outside the active attention window.

The proof gives a more explicit form: each active context stores the input plus𝒪​(log⁡T​(n))\mathcal{O}(\log T(n))auxiliary tokens for indexing the simulated time step and tape position. Thus, forT​(n)=2𝒪​(s​(n))T(n)=2^{\mathcal{O}(s(n))}, the simulation uses local contextn+𝒪​(s​(n))n+\mathcal{O}(s(n)):

𝖳𝖨𝖬𝖤​(2𝒪​(s​(n)))⊆𝖱𝖬​(n+𝒪​(s​(n)),∞,∞).\mathsf{TIME}(2^{\mathcal{O}(s(n))})\subseteq\mathsf{RM}(n+\mathcal{O}(s(n)),\infty,\infty).(7)

Remark 1: Input versus working memory.

This distinction matters when working memory is much smaller than the input length. Recursion does not make the active context shorter than the input tokens a call must read. For tasks such as Needle-in-a-Haystack, where the answer is hidden in a long input, the bottleneck is access to the long input; recursion helps only after the needed information is in the active context, or if the model has another way to retrieve the relevant input tokens.

Remark 2: Depth and runtime.

Achieving this simulation may require recursion depth2𝒪​(s​(n))2^{\mathcal{O}(s(n))}. Without memoization, repeated subcalls may inflate the total number of generated tokens; memoization can reduce this overhead, but is not part of the basic recursive model. We provide two proofs inAppendix˜FandAppendix˜G: the first expresses Turing machine computation as recursive functions, and the second uses the classical alternating-space characterization of exponential time(Arora & Barak,2009). The above results also apply to the two variants discussed in§\mathsection˜2.1.

3.3No Recursion and Shallow Recursion

Next, we show that the depth of recursion is critical to the power of recursive models: without deep recursion, the model is no more powerful than simpler context-management approaches.

Standard Autoregressive Models.

WhenD​(n)=1D(n)=1, no recursive calls are made and the model reduces to standard autoregressive models (a.k.a. CoT). While it is known that with sufficiently many intermediate steps, autoregressive models can solve any computable problem(Merrill & Sabharwal,2024; Feng et al.,2023; Li et al.,2024; Yang et al.,2025a), this comes at a significant cost:

Theorem 2(Standard Autoregressive Models / CoT).

For a standard autoregressive model (i.e., recursive model with depthD=1D=1) with local space𝒪​(S​(n))\mathcal{O}(S(n)),S​(n)≥nS(n)\geq n, we have:

𝖳𝖨𝖬𝖤​(𝒪​(S​(n)))\displaystyle\mathsf{TIME}(\mathcal{O}(S(n)))⊆𝖱𝖬​(𝒪​(S​(n)),1),\displaystyle\subseteq\mathsf{RM}(\mathcal{O}(S(n)),1),(8)𝖱𝖬​(𝒪​(S​(n)),1)\displaystyle\mathsf{RM}(\mathcal{O}(S(n)),1)⊆𝖳𝖨𝖬𝖤​(𝒪~​(S2​(n))).\displaystyle\subseteq\mathsf{TIME}(\widetilde{\mathcal{O}}(S^{2}(n))).(9)

Both inclusions follow fromMerrill & Sabharwal (2024)(Eq. (1)); the𝒪~​(⋅)\widetilde{\mathcal{O}}(\cdot)absorbs the polylogarithmic overhead of simulating𝒪​(log⁡S​(n))\mathcal{O}(\log S(n))-precision arithmetic on a Turing machine. Together, the two inclusions show that standard autoregression with context lengthS​(n)S(n)(which determines the total reasoning steps whenD​(n)=1D(n)=1) can solve all problems in𝖳𝖨𝖬𝖤​(𝒪​(S​(n)))\mathsf{TIME}(\mathcal{O}(S(n))), but its power is contained in𝖳𝖨𝖬𝖤​(𝒪~​(S2​(n)))\mathsf{TIME}(\widetilde{\mathcal{O}}(S^{2}(n))).

Compared withTheorem˜1, this gives an exponential saving in local context for these long computations: solving the same exponential-time class without recursion would require exponentially larger context. For instance, with polynomial contextS​(n)=poly​(n)S(n)=\mathrm{poly}(n), standard models are confined to𝖯\mathsf{P}, while recursive models reach𝖤𝖷𝖯𝖳𝖨𝖬𝖤\mathsf{EXPTIME}, which is beyond𝖭𝖯\mathsf{NP}and𝖯𝖲𝖯𝖠𝖢𝖤\mathsf{PSPACE}under standard assumptions.

Constant-Depth Recursion.

Constant recursion depth already improves over plain autoregression, but only up to the power of single-context management strategies such as summarization:

Theorem 3(Constant-Depth Recursive Models).

For anyS​(n)≥nS(n)\geq n, recursive models with constant recursion depthD=O​(1)D=O(1)and local space𝒪​(S​(n))\mathcal{O}(S(n))can solve any problem in𝖲𝖯𝖠𝖢𝖤​(S​(n))\mathsf{SPACE}(S(n)):

𝖲𝖯𝖠𝖢𝖤​(S​(n))⊆𝖱𝖬​(𝒪​(S​(n)),𝒪​(1)).\mathsf{SPACE}(S(n))\subseteq\mathsf{RM}(\mathcal{O}(S(n)),\mathcal{O}(1)).(10)More generally, the same construction preserves the time bound of such a simultaneous space-time simulation:

𝖳𝖬​(S​(n),T​(n))⊆𝖱𝖬​(𝒪​(S​(n)),𝒪​(1),𝒪​(T​(n))).\mathsf{TM}(S(n),T(n))\subseteq\mathsf{RM}(\mathcal{O}(S(n)),\mathcal{O}(1),\mathcal{O}(T(n))).(11)

This result shows that constant-depth recursion achieves both space and time efficiency relative to a space-S​(n)S(n), time-T​(n)T(n)computation: the local space matches the actual space complexityS​(n)S(n), and the total number of generated tokens matches the time complexityT​(n)T(n). The proof uses tail-recursive simulations; seeAppendix˜Ffor details and for the caveat about the question-preservation variant.

However, this does not exceed optimal single-context management. This computational power matches that ofsummarization(Yang et al.,2025a), which periodically compresses reasoning history to free up space (illustrated inFigure˜1(b)). In fact, as we will prove later (§\mathsection˜4),𝖲𝖯𝖠𝖢𝖤​(S​(n))\mathsf{SPACE}(S(n))is themaximumexpressive power single-context management can achieve,and constant-depth recursion therefore offers no advantage over single-context management strategies.

Yet even this upper bound is exponentially weaker than deep recursion: comparing withTheorem˜1, there is a gap from𝖲𝖯𝖠𝖢𝖤​(S​(n))\mathsf{SPACE}(S(n))to𝖳𝖨𝖬𝖤​(2𝒪​(S​(n)))\mathsf{TIME}(2^{\mathcal{O}(S(n))}). For polynomial contextS​(n)=poly​(n)S(n)=\mathrm{poly}(n), this is the gap between𝖯𝖲𝖯𝖠𝖢𝖤\mathsf{PSPACE}and𝖤𝖷𝖯𝖳𝖨𝖬𝖤\mathsf{EXPTIME}, widely believed to be strict.

4Generalization to Agentic Systems

While the recursive model in§\mathsection˜2uses a minimal fixed controller that updates a stack according to the generator’s calls and returns, real agentic systems can use richer fixed controllers around LLMs, tools, and specialized agents(Gao et al.,2025; Wang et al.,2024; Hong et al.,2024; Wu et al.,2023). This section formalizes this more general model and asks whether richer controllers are more powerful under the same local-space bound.

4.1Formalizing Recursive Agentic Systems

We call such a controller ascaffold. Given an input string, a scaffold maintains the text of one run, such as the current prompt, scratch work, and parsed fields. It chooses which strings to send to generators or tools, uses the returned strings to update the run, and may solve a subproblem by starting another scaffold run on a new input string. The caller resumes when that run returns. Formally:

Definition 3(Recursive Agentic System).

Arecursive agentic systemis a pair(𝒮,ℱ)(\mathcal{S},\mathcal{F})consisting of:

1. 1.generatorsℱ=(f1,…,fk)\mathcal{F}=(f_{1},\ldots,f_{k}), where eachfℓ:Σ∗→Σ∗f_{\ell}:\Sigma^{*}\to\Sigma^{*}models a language model or string-valued tool;
2. 2.scaffolds𝒮=(S1,…,Sm)\mathcal{S}=(S_{1},\ldots,S_{m}), where eachSiS_{i}is a deterministic controller with string input and, when it halts, string output. During execution,SiS_{i}may issue queries𝖦𝖤𝖭ℓ​(u)\mathsf{GEN}_{\ell}(u)withℓ∈[k]\ell\in[k]or𝖲𝖤𝖫𝖥j​(u)\mathsf{SELF}_{j}(u)withj∈[m]j\in[m], whereu∈Σ∗u\in\Sigma^{*}.

These queries are interpreted as follows. A query𝖦𝖤𝖭ℓ​(u)\mathsf{GEN}_{\ell}(u)sendsuuto generatorfℓf_{\ell}and returnsfℓ​(u)f_{\ell}(u). A query𝖲𝖤𝖫𝖥j​(u)\mathsf{SELF}_{j}(u)starts a new run of scaffoldSjS_{j}on inputuu; if that run returns a stringzz, the caller receiveszzand continues. Between queries, the scaffold’s control is deterministic: it may update its stored text, halt with a string output, issue another query, or continue running.§\mathsection˜J.3formalizes this controller as an oracle Turing machine variant with output, which gives a standard way to measure local workspace and query strings in the resource bounds below.

Induced functions.

The system induces one partial function for each scaffold:

ϕi𝒮,ℱ:Σ∗⇀Σ∗,i∈[m].\phi_{i}^{\mathcal{S},\mathcal{F}}:\Sigma^{*}\rightharpoonup\Sigma^{*},\qquad i\in[m].(12)The functionϕi𝒮,ℱ\phi_{i}^{\mathcal{S},\mathcal{F}}is the partial input-output function obtained by starting scaffoldSiS_{i}with the generatorsℱ\mathcal{F}. Thusϕi𝒮,ℱ​(x)=y\phi_{i}^{\mathcal{S},\mathcal{F}}(x)=yexactly when the complete run ofSiS_{i}on inputxxterminates with outputyy, with𝖦𝖤𝖭\mathsf{GEN}queries answered by the correspondingfℓf_{\ell}and𝖲𝖤𝖫𝖥\mathsf{SELF}queries evaluated as recursive scaffold runs. Every recursive call made during this run must itself return; if the root run diverges, or if some required recursive call never returns, thenϕi𝒮,ℱ​(x)\phi_{i}^{\mathcal{S},\mathcal{F}}(x)is undefined. In the oracle Turing machine formalization of§\mathsection˜J.3, this is the corresponding non-halting computation. Since recursive calls may be mutually recursive,§\mathsection˜J.4formalizes this semantics as the least tupleϕ𝒮,ℱ=(ϕ1𝒮,ℱ,…,ϕm𝒮,ℱ)\bm{\phi}^{\mathcal{S},\mathcal{F}}=(\phi_{1}^{\mathcal{S},\mathcal{F}},\ldots,\phi_{m}^{\mathcal{S},\mathcal{F}})satisfying these query rules.

Allowing several named scaffolds is only notation. A single scaffold could take a mode tag as part of its input and branch to the corresponding case; writingS1,…,SmS_{1},\ldots,S_{m}simply lets us refer to those cases separately.

The basic recursive model of§\mathsection˜2is the one-generator, one-scaffold special case: the scaffold implements the rollout in Algorithm1on the active context and then applies the stack-update rule inEquation˜2.Figure˜2illustrates three representative examples: summarization, discrete diffusion, and prover/verifier recursion. In all three, recursion depth counts nested recursive scaffold calls, not ordinary generator/tool queries or loop iterations inside one run.

Algorithm 3Summarization0:Input

xx, generator

ff, summarizer

gg, max length

LL.

1:while

¬𝗌𝗍𝗈𝗉​(x)\neg\mathsf{stop}(x)do

2:

y←f​(x)y\leftarrow f(x)⊳\trianglerightgenerate

3:if

|y|≥L|y|\geq L:

x←g​(y)x\leftarrow g(y)⊳\trianglerightsummarize

4:else:

x←yx\leftarrow y 5:return

xx

Algorithm 4Discrete Diffusion0:State

x∈(Σ∪{𝗆𝖺𝗌𝗄})nx\in(\Sigma\cup\{\mathsf{mask}\})^{n}, denoiser

ff, transition

gg.

1:while

¬𝗌𝗍𝗈𝗉​(x)\neg\mathsf{stop}(x)do

2:

y←f​(x)y\leftarrow f(x)⊳\trianglerightpredict mask-free tokens

3:

x←g​(x,y)x\leftarrow g(x,y)⊳\trianglerightnew masked sequence

4:return

xx

Algorithm 5Mutual Recursion:Prover&Verifier0:Goal

gg, seeds

s1,…,sks_{1},\ldots,s_{k}, prover

fpf_{p}, verifier

fvf_{v}.

1:defProver(g)(g):

2:for

i=1i=1to

kk:

3:

p←fp​(g,si)p\leftarrow f_{p}(g,s_{i})⊳\trianglerightgenerate proof

4:ifVerifier(g,p)=correct(g,p)=\texttt{correct}:

5:returncorrect

6:returnwrong⊳\trianglerightall failed

7:

8:defVerifier(g,p)(g,p):

9:

(𝗌𝗍𝖺𝗍𝗎𝗌,𝒢)←fv​(g,p)(\mathsf{status},\mathcal{G})\leftarrow f_{v}(g,p)⊳\trianglerightcheck proof

10:if

𝗌𝗍𝖺𝗍𝗎𝗌∈{correct,wrong}\mathsf{status}\in\{\texttt{correct},\texttt{wrong}\}:

11:return

𝗌𝗍𝖺𝗍𝗎𝗌\mathsf{status} 12:if

𝗌𝗍𝖺𝗍𝗎𝗌=incomplete\mathsf{status}=\texttt{incomplete}:

13:return

∧g′∈𝒢\wedge_{g^{\prime}\in\mathcal{G}}Prover(g′)(g^{\prime})⊳\trianglerightprove subgoals

Figure 2:Examples formalized as recursive agentic systems.Summarization(top left) has one scaffold and two generators, a generatorffand a summarizergg. The scaffold keeps a current sequencexx, queriesfffory=f​(x)y=f(x), and if|y|≥L|y|\geq Lqueriesggto compressyybefore continuing; otherwise it continues fromyy. It makes no recursive call, soD=1D=1.Discrete diffusion(bottom left) is also non-recursive: one scaffold maintains a masked sequencexx, queries the denoiserff, and applies the transition ruleg​(x,y)g(x,y)to reveal, overwrite, or re-mask positions. Iterating this refinement does not create child scaffold runs, so againD=1D=1.Prover/verifier recursion(right) uses two scaffolds,SproveS_{\mathrm{prove}}andSverifyS_{\mathrm{verify}}, and two generators,fpf_{p}andfvf_{v}. The prover usesfpf_{p}to propose candidate proofs and calls the verifier; the verifier usesfvf_{v}to accept, reject, or identify missing subgoals. If a proof is incomplete, the verifier recursively starts prover runs on the subgoals and returns their conjunction, so the recursive call tree is the proof-decomposition tree.

4.2Optimality of Recursive Models

We now compare the general scaffold model with the minimal recursive model analyzed in§\mathsection˜3. The question is whether these more general controllers can compute more under the same local-space bound. The answer is no: once local space and recursion depth are fixed, richer controllers give no additional asymptotic power.

Definition 4(LL-bounded execution).

Fix(𝒮,ℱ)(\mathcal{S},\mathcal{F})and its induced partial functionsϕ𝒮,ℱ\bm{\phi}^{\mathcal{S},\mathcal{F}}. Forr∈{1,…,m}r\in\{1,\ldots,m\}, inputx∈Σ∗x\in\Sigma^{*}, andL∈ℕL\in\mathbb{N}, evaluation ofϕr𝒮,ℱ​(x)\phi_{r}^{\mathcal{S},\mathcal{F}}(x)isLL-boundedif every scaffold invocation in the resulting recursive call tree stores at mostLLsymbols locally, including its internal workspace and any query/answer strings it currently holds. This bound is per call frame; the internal computation of generators/tools is not counted.

This is the analogue of the local space bound inDefinition˜1. Recursion depth controls how many such frames may be nested.

Unbounded Depth.

The first bound says that anyLL-bounded recursive agentic system can be simulated in time exponential in its per-call local space, relative to its generators.

Theorem 4(Upper bounds underLL-bounded executions (unbounded recursion depth)).

Fix any functionL​(n)≥nL(n)\geq n. Let(𝒮,ℱ)(\mathcal{S},\mathcal{F})be any recursive agentic system. For any indexr∈{1,…,m}r\in\{1,\ldots,m\}, any language decided byϕr𝒮,ℱ\phi_{r}^{\mathcal{S},\mathcal{F}}underL​(n)L(n)-bounded execution for input of lengthnn(Definition˜4) lies in𝖣𝖳𝖨𝖬𝖤ℱ​(2𝒪​(L​(n)))\mathsf{DTIME}^{\mathcal{F}}\bigl(2^{\mathcal{O}(L(n))}\bigr). Here𝖣𝖳𝖨𝖬𝖤ℱ\mathsf{DTIME}^{\mathcal{F}}denotes the usual relativized deterministic time class (§\mathsection˜J.3), viewing the generator/tool familyℱ\mathcal{F}as an oracle family.

In particular, if every generator/tool inℱ\mathcal{F}is computable by a deterministic Turing machine in time2𝒪​(L​(n))2^{\mathcal{O}(L(n))}and work space𝒪​(L​(n))\mathcal{O}(L(n))on all queries of length at mostL​(n)L(n), then the language lies in𝖳𝖨𝖬𝖤​(2𝒪​(L​(n)))\mathsf{TIME}(2^{\mathcal{O}(L(n))}).

Constant Depth.

If the recursion depth is constant, a depth-first simulation stores only a constant number ofLL-bounded calls, giving a space bound.

Theorem 5(Upper bounds underLL-bounded executions (constant recursion depth)).

Fix any functionL​(n)≥nL(n)\geq n. Let(𝒮,ℱ)(\mathcal{S},\mathcal{F})be any recursive agentic system. For any indexr∈{1,…,m}r\in\{1,\ldots,m\}, ifϕr𝒮,ℱ\phi_{r}^{\mathcal{S},\mathcal{F}}decides a language underL​(n)L(n)-bounded execution for input of lengthnn(Definition˜4) and the recursion stack depth isD​(n)=𝒪​(1)D(n)=\mathcal{O}(1)throughout evaluation ofϕr𝒮,ℱ\phi_{r}^{\mathcal{S},\mathcal{F}}, then the decided language lies in𝖣𝖲𝖯𝖠𝖢𝖤ℱ​(𝒪​(L​(n)))\mathsf{DSPACE}^{\mathcal{F}}\bigl(\mathcal{O}(L(n))\bigr).

In particular, if every generator/tool inℱ\mathcal{F}is computable by a deterministic Turing machine in time2𝒪​(L​(n))2^{\mathcal{O}(L(n))}and work space𝒪​(L​(n))\mathcal{O}(L(n))on all queries of length at mostL​(n)L(n), then the language lies in𝖣𝖲𝖯𝖠𝖢𝖤​(𝒪​(L​(n)))\mathsf{DSPACE}(\mathcal{O}(L(n))).

SeeAppendices˜KandLfor the proofs.

Together with the lower bounds in§\mathsection˜3, these results show that recursion, rather than the choice of controller, is the source of the gain: richer fixed controllers may be useful in practice, but they do not asymptotically exceed the simplecall/returnmodel under the same local-space and depth bounds.

5Experiments

We validate recursive models in two complementary settings. First, we evaluate end-to-end performance on SAT, where we fine-tune a pretrained base model and recursive calls implement backtracking search. Second, we evaluate 4x4 Go position traces generated by an exact game-tree solver, where a model is trained from scratch and evaluated by trace-level accuracy. Code is available atchr26195/RecursiveModel.

Table 1:Accuracy (%) on SAT instances. Baseline results fromWei et al. (2025). Ours is fine-tuned from Qwen2.5-3B-Instruct.ModelEasyMediumHardRandom Baseline50.050.050.0DeepSeek-Distill-14B84.355.246.4LLaMA3.3-70B65.158.152.9Qwen3-235B88.064.851.4GPT-4o69.955.248.8Recursive Model (ours)989564 Table 2:Trace accuracy (%) on 4x4 Go. IID uses held-out random positions from the same distribution as training; Length-OOD trains on shorter solver traces and evaluates on longer traces.MethodIIDLength-OODCoT73.41.0PENCIL71.05.6Recursive Model (ours)91.838.5

5.1Experimental Setup

Training setup.

We train on supervised reasoning traces rather than final answers alone, but use different model regimes for the two experiments. For SAT, we fine-tune a pretrained Qwen2.5-3B-Instruct model. For Go, we train a 4-layer, 4-head decoder-only Transformer with width 256 (3.18M parameters) from scratch on traces produced by the exact solver. In both settings, the trace specifies not only the final answer but also the local decisions made during the recursive computation.

Training examples and loss.

We convert each trace into next-token prediction data by replaying its execution. At each step, the conditioning text is the context that would be visible to the method being trained: for the recursive model, this is the current active frame; for single-context baselines, it is the corresponding rendered single sequence. The target is the next local continuation in that context, ending at acall, areturn, or the final answer. Scaffold-provided tokens, such as a child answer inserted back into the parent after a return, may appear in the context but are not included in the loss. We minimize the standard decoder-only language-modeling loss on supervised continuation tokens only. Thus, for the recursive model, suspended parent or child frames are not concatenated into the conditioning text; equivalently, this visibility constraint can be implemented with an attention mask.

SAT.

We evaluate on SAT, a canonical NP-complete problem: given Boolean variables and clauses, decide whether some assignment satisfies all clauses. The recursive model is trained to follow a DPLL-style backtracking trace. Each frame contains the original puzzle, the current partial assignment, and the clauses simplified under that assignment. It returnsYesorNoif the branch is already solved or contradictory; otherwise, it emits acallwith one extra variable assignment. The child solves this restricted formula, and the parent either accepts the satisfying branch or tries the opposite assignment. Thus a long search tree is executed as many small local decisions rather than one monolithic transcript. We adopt instances fromWei et al. (2025), converted to natural language puzzles, and generate traces in this recursive format. Details appear in§\mathsection˜B.1.

For the SAT fine-tuning experiment, we make two practical adaptations. First, uponreturn, we preserve the subtask description and answer in the parent context so the parent knows what was asked and solved. Second, we prepend the root problem to every recursive context so all subtasks retain access to the global objective. See§\mathsection˜B.3for details.

Go.

We also test 4x4 Go position evaluation: decide whether the player to move can force a win. The exact solver first labels terminal states by area scoring, propagates forcedWin/Losevalues backward through the finite game graph, and assigns all remaining states the draw valueU. We train only on roots whose canonical proof trace queriesWin/Losestates. The recursive trace asks the model to reproduce this proof tree throughcall/return: a parent calls a child board, the child returns onlyWinorLose, and the parent uses that value to keep searching or return its own label. As in the implementation, child proofs stay in separate frames: the parent receives the child result, not the full child trace. We train matched CoT and PENCIL(Yang et al.,2025a)baselines and our recursive model on the same traces. PENCIL is a single-context context-management baseline: the computation stays in one running context, but the model can erase intermediate reasoning and keep summaries. All methods use the same 3.18M-parameter decoder-only Transformer and 64K updates. The IID split uses 80K/10K positions; length-OOD trains on shorter traces and tests on longer ones. SeeAppendix˜Cfor details.

5.2Results

SAT Accuracy.

We fine-tune Qwen2.5-3B-Instruct with our recursive framework (see§​§\mathsection\mathsection˜B.1andB.2for data splits and training details) and compare against frontier LLMs with standard prompting, including GPT-4o, LLaMA3.3-70B, and Qwen3-235B. Table2reports end-to-end answer accuracy: an instance is counted as correct only when the final satisfiable/unsatisfiable answer is correct. The model is trained only on easy and medium instances, while the hard split contains more clauses and is held out from training; thus hard accuracy tests whether the learned backtracking procedure transfers to harder searches. As Table2shows, the prompted baselines degrade as difficulty increases, with hard-instance accuracy close to chance. In contrast, our recursive model achieves 98% on easy and 95% on medium instances, substantially outperforming the baselines. More importantly, it reaches 64% on hard instances despite never training on that difficulty level. This suggests that the gain is not only from fitting the answer distribution, but from learning to execute the recursive backtracking structure on harder formulas.

Go Accuracy.

Table2reports trace accuracy for Go: whether the model reproduces the solver’s search trace on a held-out position. On IID positions, all three methods learn nontrivial traces, but the recursive format is strongest, reaching 91.8% compared with 73.4% for CoT and 71.0% for PENCIL. The gap is larger in the length-OOD split, where test boards require longer searches than those seen during training. In this setting, CoT and PENCIL rarely reproduce the full trace (1.0% and 5.6%), while the recursive model remains at 38.5%.Figure˜3shows the same pattern over training: the recursive model converges faster on the training split, and this faster fit is accompanied by substantially better trace accuracy on the length-OOD test split.

Figure 3:Length-OOD Go trace accuracy during training. Dashed lines evaluate on the training split; solid lines evaluate on the length-OOD test split. The vertical dashed line marks the learning-rate drop from3×10−43\times 10^{-4}to3×10−53\times 10^{-5}at 32K updates.Figure 4:Trajectory length vs. active context length.We also measure end-to-end final-label accuracy on the IID split, which ignores the trace and checks only whether the rollout ends with the correct rootWin/Loselabel. This number is high for all three methods (96.9%, 96.5%, and 99.2%). We do not view this alone as evidence that all methods learned the intended search: because the label is binary and the board is small, a model can sometimes reach the right label through shortcuts or through an invalid partial trace that happens to end with the right answer. As a stricter rollout check, we count a final label only when the generated trace can be parsed and replayed as a valid solver proof: each proposed move must be legal, child returns must agree with the exact child labels, and parentWin/Losedecisions must follow the game-tree rule. Under this check, the recursive model is again strongest: 96.9%, compared with 81.6% for CoT and 90.6% for PENCIL.

Context Efficiency.

Across both tasks, recursive models separate total work from active context. Definetrajectory lengthas the total tokens generated across all recursive calls, andactive context lengthas the maximum number of visible tokens used at any step. Figure4shows that trajectory length grows rapidly with problem size, while active context length stays bounded. For Go, we measure active context directly from each method’s visibility mask on all 10K IID held-out roots. The maximum is 16,356 tokens for CoT, 595 for PENCIL, and 54 for the recursive model, a303×303\timesreduction over CoT and an11×11\timesreduction over PENCIL.

6Discussion

6.1Inference Efficiency

Recursion significantly reduces inference cost by decoupling stack capacity from attention cost. Any single-context model, even those with proper context management strategies such as summarization, must attend to all preceding tokens in the sequence, incurring𝒪​(|𝐱t|)\mathcal{O}(|\mathbf{x}_{t}|)FLOPs with KV cache at each steptt. In contrast, recursive models bound the active context to|𝐒t​[−1]|≤𝖫𝖲​(𝐒t)|\mathbf{S}_{t}[-1]|\leq\mathsf{LS}(\mathbf{S}_{t}), therefore requiring only𝒪​(𝖫𝖲​(𝐒t))\mathcal{O}(\mathsf{LS}(\mathbf{S}_{t}))FLOPs per token. This is a𝖦𝖲​(𝐒t)/𝖫𝖲​(𝐒t)\mathsf{GS}(\mathbf{S}_{t})/\mathsf{LS}(\mathbf{S}_{t})times speedup over the baseline that works on a single sequence, and larger speedup compared with standard CoT that does not manage the context at all. To achieve this speedup, we assume in implementation, KV caches of suspended contexts are stored in external storage and restored upon return, avoiding recomputation.

6.2Heterogeneous Model Selection and Tool-Use

The recursive structure of recursive models naturally supports heterogeneous model selection(Ye et al.,2025; Zhang et al.,2025b; Agashe et al.,2025): instead of always calling itself, the model can invoke different models to handle different subtasks, such as larger models for complex reasoning and smaller models for routine operations. This strikes a natural tradeoff between capability and cost, allowing the overall expense and latency to scale with actual task complexity rather than being dominated by the most expensive model in the system.

6.3Error Accumulation

A potential risk of recursive models is error accumulation: mistakes in subtasks may propagate and corrupt the final answer, especially as recursion depth grows. This concern, however, is not unique to recursion: if CoT produces the same long trajectory as recursive models, a single mistake could propagate as well. Moreover, recursive models offer partial mitigation that CoT lacks: uponreturn, the intermediate reasoning within a subtask is discarded, so errors made there do not pollute sibling or parent computations.

7Related Work

Recursion in Language Modeling.

Some prior work has explored the idea of recursion in language models. However, these approaches are limited in several ways.First, many methods only support shallow recursion (depth=1=1) or context folding(Sun et al.,2025; Zhang et al.,2025a; Pan et al.,2025), which we prove inTheorem˜3to be no more powerful than summarization-based single-context models. The concurrent work ofZhang et al. (2025a)focuses on decomposing long inputs, whereas our work studies recursive organization of the reasoning process and proves why recursion depth is the key resource.Second, many rely on prompting frozen models to follow recursive patterns(Schroeder et al.,2025; Prasad et al.,2024; Zhang et al.,2025c).Third, prior work often targets specific scenarios: arithmetic with fixed recursive patterns(Lee & Kim,2023), rigid Planner-Executor architectures(Prasad et al.,2024; Zhang et al.,2025c), or context extension via input chunking(Zhang et al.,2025a). This paper provides a general formalization of recursive models, both in its simplest form and generalized form in agentic systems. Our theoretical analysis highlights the critical role of recursion depth: constant-depth recursion offers no advantage over single-context models, whereas unbounded depth unlocks exponentially greater computational power.

Agentic Systems and Context Management.

LLM-based agentic systems (seeGao et al. (2025); Wang et al. (2024)and references therein) provide a natural setting for recursion: they decompose tasks into modular subtasks handled by agents or tools, often in separate contexts. A related line of work studies how to keep long computations within a bounded context, includingsummarizationthat compresses context into compact representations(Yang et al.,2025a; Yu et al.,2025; Zhou et al.,2025; Yan et al.,2025; Wu et al.,2025), andmemory augmentationthat maintains external storage for retrieval(Packer et al.,2024; Chhikara et al.,2025; Suzgun et al.,2025; Xu et al.,2025). These approaches address the same pressure from long contexts, but at different levels: agentic systems provide modular control, while context-management methods compress or retrieve information inside a run. Formal analysis remains limited; notable exceptions areYang et al. (2025a,b), which focus on summarization and diffusion models respectively.

Recursion in Classical Computation Theory.

Although the idea that recursion depth and local space are fundamental computational resources has classical roots(Savitch,1977; Ginsburg et al.,1967; Aho,1969; Engelfriet,1991; Savitch,1970), our work introduces recursion as an explicit design principle for Transformer-based reasoning and proves that constant-depth Transformers can realize the per-step logic at each recursion level (seeAppendix˜Afor detailed discussion). More broadly, our results suggest that scaling LLM reasoning need not rely solely on extending context length: a lightweight recursive scaffold that requires no architectural changes can leverage bounded context exponentially more efficiently. Just as recursion transformed programming from flat instruction sequences to modular, composable programs, it may similarly transform LLM reasoning from monolithic chain-of-thought into structured, hierarchical computation.

8Conclusion

We identify recursion as a core principle for overcoming context constraints and propose recursive models as a minimal yet powerful realization. We show that recursion exponentially reduces the required context length compared to single-context approaches, and this power is optimal among all recursive agentic systems. Experiments on SAT and controlled game-tree evaluation validate that models trained with recursive reasoning can significantly improve long-horizon reasoning while keeping active contexts small.

Impact Statement

This paper presents a theoretical understanding of recursive models and suggests an approach to enhance the long-horizon reasoning capabilities of language models. We do not foresee any direct negative societal impact from this work, unless AI systems are employed for unethical purposes, which is a general concern applicable to all advances in machine learning.

References

• Agashe et al. (2025)Agashe, S., Wong, K., Tu, V., Yang, J., Li, A., and Wang, X. E.Agent S2: A compositional generalist-specialist framework for computer use agents.arXiv preprint arXiv:2504.00906, 2025.
• Aho (1969)Aho, A. V.Nested stack automata.Journal of the ACM, 16(3):383–406, 1969.doi:10.1145/321526.321529.
• Arora & Barak (2009)Arora, S. and Barak, B.Computational Complexity: A Modern Approach.Cambridge University Press, 2009.
• Brown et al. (2020)Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al.Language models are few-shot learners.Advances in Neural Information Processing Systems, 33:1877–1901, 2020.URLhttps://proceedings.neurips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html.
• Chandra et al. (1981)Chandra, A. K., Kozen, D. C., and Stockmeyer, L. J.Alternation.Journal of the ACM, 28(1):114–133, 1981.doi:10.1145/322234.322243.
• Chhikara et al. (2025)Chhikara, P., Khant, D., Aryan, S., Singh, T., and Yadav, D.Mem0: Building production-ready AI agents with scalable long-term memory, 2025.URLhttps://arxiv.org/abs/2504.19413.
• DeepSeek-AI et al. (2025)DeepSeek-AI, Guo, D., Yang, D., Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma, S., Wang, P., Bi, X., et al.DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning.arXiv preprint arXiv:2501.12948, 2025.URLhttps://arxiv.org/abs/2501.12948.
• Engelfriet (1991)Engelfriet, J.Iterated stack automata and complexity classes.Information and Computation, 95(1):21–75, 1991.doi:10.1016/0890-5401(91)90015-T.
• Feng et al. (2023)Feng, G., Zhang, B., Gu, Y., Ye, H., He, D., and Wang, L.Towards revealing the mystery behind chain of thought: A theoretical perspective.InAdvances in Neural Information Processing Systems, volume 36, 2023.URLhttps://papers.nips.cc/paper_files/paper/2023/hash/dfc310e81992d2e4cedc09ac47eff13e-Abstract-Conference.html.
• Gao et al. (2025)Gao, H.-a., Geng, J., Hua, W., Hu, M., Juan, X., Liu, H., Liu, S., Qiu, J., Qi, X., Wu, Y., Wang, H., Xiao, H., Zhou, Y., Zhang, S., Zhang, J., Xiang, J., Fang, Y., Zhao, Q., Liu, D., Ren, Q., Qian, C., Wang, Z., Hu, M., Wang, H., Wu, Q., Ji, H., and Wang, M.A survey of self-evolving agents: What, when, how, and where to evolve on the path to artificial super intelligence.arXiv preprint arXiv:2507.21046, 2025.URLhttps://arxiv.org/abs/2507.21046.
• Ginsburg et al. (1967)Ginsburg, S., Greibach, S. A., and Harrison, M. A.One-way stack automata.Journal of the ACM, 14(2):389–418, 1967.doi:10.1145/321386.321403.
• Hong et al. (2024)Hong, S., Zheng, X., Chen, J., Cheng, Y., Wang, J., Zhang, C., Wang, Z., Yau, S. K. S., Lin, Z., Zhou, L., et al.MetaGPT: Meta programming for a multi-agent collaborative framework.InInternational Conference on Learning Representations, 2024.URLhttps://openreview.net/forum?id=VtmBAGCN7o.
• Lee & Kim (2023)Lee, S. and Kim, G.Recursion of thought: A divide-and-conquer approach to multi-context reasoning with language models.arXiv preprint arXiv:2306.06891, 2023.URLhttps://arxiv.org/abs/2306.06891.
• Li et al. (2023)Li, G., Hammoud, H., Itani, H., Khizbullin, D., and Ghanem, B.CAMEL: Communicative agents for “mind” exploration of large language model society.InAdvances in Neural Information Processing Systems, volume 36, pp. 51991–52008. Curran Associates, Inc., 2023.URLhttps://proceedings.neurips.cc/paper_files/paper/2023/file/a3621ee907def47c1b952ade25c67698-Paper-Conference.pdf.
• Li et al. (2024)Li, Z., Liu, H., Zhou, D., and Ma, T.Chain of thought empowers transformers to solve inherently serial problems.InInternational Conference on Learning Representations, 2024.URLhttps://openreview.net/forum?id=3EWTEy9MTM.
• Merrill & Sabharwal (2024)Merrill, W. and Sabharwal, A.The expressive power of transformers with chain of thought.InInternational Conference on Learning Representations, 2024.URLhttps://openreview.net/forum?id=NjNGlPh8Wh.
• Merrill et al. (2022)Merrill, W., Sabharwal, A., and Smith, N. A.Saturated transformers are constant-depth threshold circuits.Transactions of the Association for Computational Linguistics, 10:843–856, 2022.doi:10.1162/tacl_a_00493.URLhttps://aclanthology.org/2022.tacl-1.49/.
• OpenAI (2024)OpenAI.Learning to reason with LLMs, September 2024.URLhttps://openai.com/index/learning-to-reason-with-llms/.
• OpenAI et al. (2023)OpenAI, Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al.GPT-4 technical report.arXiv preprint arXiv:2303.08774, 2023.URLhttps://arxiv.org/abs/2303.08774.
• Packer et al. (2024)Packer, C., Wooders, S., Lin, K., Fang, V., Patil, S. G., Stoica, I., and Gonzalez, J. E.MemGPT: Towards LLMs as operating systems, 2024.URLhttps://arxiv.org/abs/2310.08560.
• Pan et al. (2025)Pan, J., Li, X., Lian, L., Snell, C., Zhou, Y., Yala, A., Darrell, T., Keutzer, K., and Suhr, A.Learning adaptive parallel reasoning with language models.arXiv preprint arXiv:2504.15466, 2025.URLhttps://arxiv.org/abs/2504.15466.
• Park et al. (2023)Park, J. S., O’Brien, J., Cai, C. J., Morris, M. R., Liang, P., and Bernstein, M. S.Generative agents: Interactive simulacra of human behavior.InProceedings of the 36th Annual ACM Symposium on User Interface Software and Technology, pp. 1–22. ACM, 2023.doi:10.1145/3586183.3606763.URLhttps://dl.acm.org/doi/10.1145/3586183.3606763.
• Prasad et al. (2024)Prasad, A., Koller, A., Hartmann, M., Clark, P., Sabharwal, A., Bansal, M., and Khot, T.ADaPT: As-needed decomposition and planning with language models.InFindings of the Association for Computational Linguistics: NAACL 2024, pp. 4226–4252, Mexico City, Mexico, Jun 2024. Association for Computational Linguistics.doi:10.18653/v1/2024.findings-naacl.264.URLhttps://aclanthology.org/2024.findings-naacl.264/.
• Qwen Team (2025)Qwen Team.Qwen2.5 technical report, 2025.URLhttps://arxiv.org/abs/2412.15115.
• Radford et al. (2018)Radford, A., Narasimhan, K., Salimans, T., and Sutskever, I.Improving language understanding by generative pre-training.OpenAI technical report, 2018.URLhttps://cdn.openai.com/research-covers/language-unsupervised/language_understanding_paper.pdf.
• Radford et al. (2019)Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., Sutskever, I., et al.Language models are unsupervised multitask learners.OpenAI technical report, 2019.URLhttps://cdn.openai.com/better-language-models/language_models_are_unsupervised_multitask_learners.pdf.
• Savitch (1970)Savitch, W. J.Relationships between nondeterministic and deterministic tape complexities.Journal of Computer and System Sciences, 4(2):177–192, 1970.doi:10.1016/S0022-0000(70)80006-X.
• Savitch (1977)Savitch, W. J.Recursive Turing machines.International Journal of Computer Mathematics, 6(1):3–31, 1977.doi:10.1080/00207167708803124.
• Schroeder et al. (2025)Schroeder, P., Morgan, N. W., Luo, H., and Glass, J. R.THREAD: Thinking deeper with recursive spawning.InProceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pp. 8418–8442, Albuquerque, New Mexico, Apr 2025. Association for Computational Linguistics.doi:10.18653/v1/2025.naacl-long.427.URLhttps://aclanthology.org/2025.naacl-long.427/.
• Shinn et al. (2023)Shinn, N., Cassano, F., Gopinath, A., Narasimhan, K., and Yao, S.Reflexion: Language agents with verbal reinforcement learning.Advances in Neural Information Processing Systems, 36:8634–8652, 2023.URLhttps://proceedings.neurips.cc/paper_files/paper/2023/file/1b44b878bb782e6954cd888628510e90-Paper-Conference.pdf.
• Sun et al. (2025)Sun, W., Lu, M., Ling, Z., Liu, K., Yao, X., Yang, Y., and Chen, J.Scaling long-horizon LLM agent via context-folding, 2025.URLhttps://arxiv.org/abs/2510.11967.
• Suzgun et al. (2025)Suzgun, M., Yuksekgonul, M., Bianchi, F., Jurafsky, D., and Zou, J.Dynamic cheatsheet: Test-time learning with adaptive memory.arXiv preprint arXiv:2504.07952, 2025.URLhttps://arxiv.org/abs/2504.07952.
• Wang et al. (2024)Wang, L., Ma, C., Feng, X., Zhang, Z., Yang, H., Zhang, J., Chen, Z., Tang, J., Chen, X., Lin, Y., Zhao, W. X., Wei, Z., and Wen, J.A survey on large language model based autonomous agents.Frontiers of Computer Science, 18(6):186345, 2024.doi:10.1007/s11704-024-40231-1.URLhttps://link.springer.com/article/10.1007/s11704-024-40231-1.
• Wei et al. (2025)Wei, A., Wu, Y., Wan, Y., Suresh, T., Tan, H., Zhou, Z., Koyejo, S., Wang, K., and Aiken, A.SATBench: Benchmarking LLMs’ logical reasoning via automated puzzle generation from SAT formulas.InProceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pp. 33832–33849, Suzhou, China, Nov 2025. Association for Computational Linguistics.doi:10.18653/v1/2025.emnlp-main.1716.URLhttps://aclanthology.org/2025.emnlp-main.1716/.
• Wei et al. (2022)Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E., Le, Q. V., and Zhou, D.Chain-of-thought prompting elicits reasoning in large language models.Advances in Neural Information Processing Systems, 35:24824–24837, 2022.URLhttps://proceedings.neurips.cc/paper_files/paper/2022/file/9d5609613524ecf4f15af0f7b31abca4-Paper-Conference.pdf.
• Wu et al. (2023)Wu, Q., Bansal, G., Zhang, J., Wu, Y., Li, B., Zhu, E., Jiang, L., Zhang, X., Zhang, S., Liu, J., Awadallah, A. H., White, R. W., Burger, D., and Wang, C.AutoGen: Enabling next-gen LLM applications via multi-agent conversation, 2023.
• Wu et al. (2025)Wu, X., Li, K., Zhao, Y., Zhang, L., Ou, L., Yin, H., Zhang, Z., Yu, X., Zhang, D., Jiang, Y., Xie, P., Huang, F., Cheng, M., Wang, S., Cheng, H., and Zhou, J.ReSum: Unlocking long-horizon search intelligence via context summarization, 2025.URLhttps://arxiv.org/abs/2509.13313.
• Xu et al. (2025)Xu, W., Liang, Z., Mei, K., Gao, H., Tan, J., and Zhang, Y.A-MEM: Agentic memory for LLM agents.arXiv preprint arXiv:2502.12110, 2025.URLhttps://arxiv.org/abs/2502.12110.
• Yan et al. (2025)Yan, S., Yang, X., Huang, Z., Nie, E., Ding, Z., Li, Z., Ma, X., Bi, J., Kersting, K., Pan, J. Z., Schütze, H., Tresp, V., and Ma, Y.Memory-R1: Enhancing large language model agents to manage and utilize memories via reinforcement learning.arXiv preprint arXiv:2508.19828, 2025.URLhttps://arxiv.org/abs/2508.19828.
• Yang et al. (2025a)Yang, C., Srebro, N., McAllester, D., and Li, Z.PENCIL: Long thoughts with short memory.arXiv preprint arXiv:2503.14337, 2025a.URLhttps://arxiv.org/abs/2503.14337.
• Yang et al. (2025b)Yang, C., Zhou, C., Wipf, D., and Li, Z.On powerful ways to generate: Autoregression, diffusion, and beyond.arXiv preprint arXiv:2510.06190, 2025b.URLhttps://arxiv.org/abs/2510.06190.
• Yao et al. (2023)Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K., and Cao, Y.ReAct: Synergizing reasoning and acting in language models.InInternational Conference on Learning Representations, 2023.URLhttps://openreview.net/forum?id=WE_vluYUL-X.
• Ye et al. (2025)Ye, R., Liu, X., Wu, Q., Pang, X., Yin, Z., Bai, L., and Chen, S.X-MAS: Towards building multi-agent systems with heterogeneous LLMs.arXiv preprint arXiv:2505.16997, 2025.URLhttps://arxiv.org/abs/2505.16997.
• Yu et al. (2025)Yu, H., Chen, T., Feng, J., Chen, J., Dai, W., Yu, Q., Zhang, Y.-Q., Ma, W.-Y., Liu, J., Wang, M., and Zhou, H.MemAgent: Reshaping long-context LLM with multi-conv RL-based memory agent.arXiv preprint arXiv:2507.02259, 2025.URLhttps://arxiv.org/abs/2507.02259.
• Zhang et al. (2025a)Zhang, A. L., Kraska, T., and Khattab, O.Recursive language models.arXiv preprint arXiv:2512.24601, 2025a.URLhttps://arxiv.org/abs/2512.24601.
• Zhang et al. (2025b)Zhang, G., Chen, K., Wan, G., Chang, H., Cheng, H., Wang, K., Hu, S., and Bai, L.EvoFlow: Evolving diverse agentic workflows on the fly.arXiv preprint arXiv:2502.07373, 2025b.URLhttps://arxiv.org/abs/2502.07373.
• Zhang et al. (2025c)Zhang, Z., Chen, T., Xu, W., Pentland, A., and Pei, J.ReCAP: Recursive context-aware reasoning and planning for large language model agents.arXiv preprint arXiv:2510.23822, 2025c.URLhttps://arxiv.org/abs/2510.23822.
• Zhou et al. (2025)Zhou, Z., Qu, A., Wu, Z., Kim, S., Prakash, A., Rus, D., Zhao, J., Low, B. K. H., and Liang, P. P.MEM1: Learning to synergize memory and reasoning for efficient long-horizon agents.arXiv preprint arXiv:2506.15841, 2025.URLhttps://arxiv.org/abs/2506.15841.

Appendix ARecursion in Classical Computation Theory

The idea that recursion depth and local space are fundamental computational resources has deep roots in classical theory. Most directly related to our work,Savitch (1977)formally extended Turing machines with recursive subroutine calls—each call receives its own workspace and returns a result to the caller, mirroring the call/return and context-stack mechanism of our recursive models. Savitch studied the time and storage overhead of recursion, showing thatttsteps of a recursive TM can be simulated inO​(t)O(t)steps on a multitape TM, and used this framework to re-derive the𝖭𝖲𝖯𝖠𝖢𝖤​(S)⊆𝖣𝖲𝖯𝖠𝖢𝖤​(S2)\mathsf{NSPACE}(S)\subseteq\mathsf{DSPACE}(S^{2})result of Savitch’s theorem(Savitch,1970)—whose proof is itself a recursive subroutine with bounded stack depth, where recursion depth times per-level workspace yields the total space upper bound, foreshadowing our local-vs-global space decomposition. The key difference is that Savitch’s recursive TM reads one tape cell per step (O​(1)O(1)communication), and therefore already captures𝖲𝖯𝖠𝖢𝖤​(S)\mathsf{SPACE}(S)without needing deep recursion. Our recursive model replaces the TM head with a bounded-context Transformer that attends to allS​(n)S(n)tokens per step; it is this architectural constraint that makes deep recursion necessary to recover the same computational power. Stack automata(Ginsburg et al.,1967)extend pushdown automata by allowing the head to read within the stack, and nested stack automata(Aho,1969)further allow the creation and destruction of substacks, yielding a stack-of-stacks mechanism reminiscent of our context stack.Engelfriet (1991)studied iterated (higher-order) pushdown storages and established an iterated-exponential hierarchy in computational power as the storage order increases—a phenomenon consistent with ourTheorem˜1andTheorem˜3. The alternation theorem(Chandra et al.,1981), which we directly use in our proofs, connects alternating computation to space complexity via a recursive evaluation of configuration games.

Our contribution relative to this classical line of work is twofold. First, we introduce recursion as an explicit design principle for Transformer-based reasoning, formalizing how bounded-context language models can overcome their attention bottleneck through recursive self-invocation. Second, we proveTransformer realizability: a fixed constant-depth, constant-size Transformer with𝒪​(log⁡S​(n))\mathcal{O}(\log S(n))precision can implement the per-step logic at each recursion level, serving as the transition function of a recursive machine. This bridges the classical recursion-theoretic framework with the concrete capabilities of modern neural architectures.

Appendix BExperimental Setup (SAT)

B.1Data Generation

We directly use the SAT instances fromWei et al. (2025), which are Boolean formulas in conjunctive normal form (CNF). Each instance is converted to a natural language puzzle where variables map to real-world entities and clauses become narrative constraints. The dataset contains instances of varying difficulty based on the number of clauses: easy (4–19 clauses), medium (20–30 clauses), and hard (31–50 clauses).

For each instance, we generate a recursive reasoning trace by running the DPLL algorithm. At each step, the algorithm picks an unassigned variable and tries assigning it to True. After each assignment, we check for conflicts: either a clause becomes empty (directly violated), or unit clauses force the same variable to both True and False. If a conflict is detected, the algorithm backtracks and tries False. We emit<call>when branching and<return>when returning. These traces are used for supervised fine-tuning.

For training, we select only easy and medium instances with at most 15 variables. For evaluation, we randomly sample 100 held-out instances from each difficulty level (easy, medium, hard) without any filtering.

B.2Training Configuration

We fine-tune from Qwen2.5-3B-Instruct(Qwen Team,2025), a decoder-only Transformer with 3 billion parameters. We use the AdamW optimizer with a learning rate of1×10−51\times 10^{-5}and cosine decay schedule. The batch size is 16 with gradient checkpointing enabled. We train for 10 epochs with a maximum context length of 4096 tokens (left truncation for sequences exceeding this limit). Training is conducted on 2×\timesNVIDIA H200 GPUs and takes approximately 8 hours.

B.3Implementation

When<call>is generated, only the reasoning before the tag is preserved in the parent context; the tag content becomes the child’scurrent_task. When<return>is generated, the subtask description and return value are appended to the parent context in the format “subtask_desc. The answer is:result.” while the intermediate reasoning within the subtask is discarded. Each context is wrapped with the following template:

[Instructions]

Solveproblemsrecursively.Use<call></call>todecompose

theproblemand<return></return>toreturntheanswer.

[RootProblem]

{root_problem}

[CurrentTask]

{current_task}

Theroot_problemfield contains the original problem statement and remains constant across all recursion levels. Thecurrent_taskfield contains the subtask description for the current level (equal toroot_problemat the top level).

B.4Sample Problems

Each training sample consists of three parts:user(the prompt),assistant_prefix(previous reasoning to continue from), andassistant_content(the target to predict). Below we show two representative turns.

Example 1:<call>at root level.

The model analyzes clauses and branches on a variable:

#user

[Instructions]

Solveproblemsrecursively.Use<call></call>todecomposetheproblemand<return></return>toreturntheanswer.

[RootProblem]

Fivescientists--Alice,Bob,Carol,Dave,andEve--areconsideringwhethertojoinanewresearchproject.Eachscientistmakesanindependentdecisionabouttheirparticipation.Theymaychoosetojoinornotjointheprojectregardlessofothers’choices.

Conditions:

1.EitherAlicejoinstheprojectorCaroldoesnotjoin.

2.EitherAlicedoesnotjoinorCaroljoins.

3.EitherAlicejoinsorCaroljoins.

4.EitherAlicedoesnotjoinorCaroldoesnotjoin.

5.EitherCaroldoesnotjoinorEvedoesnotjoin.

Isthereawaytoassigndecisionssoalltheseconditionsaresatisfied?

[CurrentTask]

Isthereawaytoassigndecisionssoalltheseconditionsaresatisfied?

#assistant_prefix

(empty)

#assistant_content

Condition1:

Clause:(Alicev~Carol)

(nosimplificationneeded)

->(notunit)

Condition2:

Clause:(~AlicevCarol)

(nosimplificationneeded)

->(notunit)

Condition3:

Clause:(AlicevCarol)

(nosimplificationneeded)

->(notunit)

Condition4:

Clause:(~Alicev~Carol)

(nosimplificationneeded)

->(notunit)

Condition5:

Clause:(~Carolv~Eve)

(nosimplificationneeded)

->(notunit)

Nounitclausefound.Unassigned:[Alice,Carol,Eve]

TryAlice=True

<call>Alice=True</call>

Example 2:<return>at leaf node.

The model detects a contradiction and returns:

#user

[Instructions]

Solveproblemsrecursively.Use<call></call>todecomposetheproblemand<return></return>toreturntheanswer.

[RootProblem]

Fivescientists--Alice,Bob,Carol,Dave,andEve--areconsideringwhethertojoinanewresearchproject.Eachscientistmakesanindependentdecisionabouttheirparticipation.Theymaychoosetojoinornotjointheprojectregardlessofothers’choices.

Conditions:

1.EitherAlicejoinstheprojectorCaroldoesnotjoin.

2.EitherAlicedoesnotjoinorCaroljoins.

3.EitherAlicejoinsorCaroljoins.

4.EitherAlicedoesnotjoinorCaroldoesnotjoin.

5.EitherCaroldoesnotjoinorEvedoesnotjoin.

Isthereawaytoassigndecisionssoalltheseconditionsaresatisfied?

[CurrentTask]

Alice=True,Carol=True

#assistant_prefix

(empty)

#assistant_content

Given:Alice=True,Carol=True

Condition1:

Clause:(Alicev~Carol)

->satisfied

Condition2:

Clause:(~AlicevCarol)

->satisfied

Condition3:

Clause:(AlicevCarol)

->satisfied

Condition4:

Clause:(~Alicev~Carol)

Simplifyas:()->CONFLICT

Contradiction!

<return>No</return>

Example 3:<call>with prefix (backtracking).

After trying Alice=True and receiving “No”, the model backtracks and tries Alice=False:

#user

[Instructions]

Solveproblemsrecursively.Use<call></call>todecomposetheproblemand<return></return>toreturntheanswer.

[RootProblem]

Fivescientists--Alice,Bob,Carol,Dave,andEve--areconsideringwhethertojoinanewresearchproject.Eachscientistmakesanindependentdecisionabouttheirparticipation.Theymaychoosetojoinornotjointheprojectregardlessofothers’choices.

Conditions:

1.EitherAlicejoinstheprojectorCaroldoesnotjoin.

2.EitherAlicedoesnotjoinorCaroljoins.

3.EitherAlicejoinsorCaroljoins.

4.EitherAlicedoesnotjoinorCaroldoesnotjoin.

5.EitherCaroldoesnotjoinorEvedoesnotjoin.

Isthereawaytoassigndecisionssoalltheseconditionsaresatisfied?

[CurrentTask]

Isthereawaytoassigndecisionssoalltheseconditionsaresatisfied?

#assistant_prefix

Condition1:

Clause:(Alicev~Carol)

(nosimplificationneeded)

->(notunit)

Condition2:

Clause:(~AlicevCarol)

(nosimplificationneeded)

->(notunit)

Condition3:

Clause:(AlicevCarol)

(nosimplificationneeded)

->(notunit)

Condition4:

Clause:(~Alicev~Carol)

(nosimplificationneeded)

->(notunit)

Condition5:

Clause:(~Carolv~Eve)

(nosimplificationneeded)

->(notunit)

Nounitclausefound.Unassigned:[Alice,Carol,Eve]

TryAlice=True

Alice=True.Theansweris:No.

#assistant_content

TryAlice=False

<call>Alice=False</call>

Appendix CExperimental Setup (Go)

C.1Task and Trace Generation

We model the Go experiment as a finite, perfect-information game graph. A state records the board position, player to move, and ko state under a fixed 4x4 placement-Go rule set. Terminal states are positions with no legal placement move. They are scored by area scoring with komi1/21/2, so every terminal state has a strict board winner; the terminal value isWinif that winner is the player to move andLoseotherwise. All values below are relative to the player to move.

We then propagate these terminal values backward through the game graph. Formally, we construct

V:𝒮→{Win,Lose,U}.V:\mathcal{S}\to\{\texttt{Win},\texttt{Lose},\texttt{U}\}.Starting from the terminal values, we repeatedly apply the standard forcing rules: a nonterminal state is markedWinonce it has some legal successor markedLose, and is markedLoseonce all of its legal successors have been markedWin. When this propagation reaches a fixed point, every still-unmarked state is assignedU. ThusUis the draw value: it consists exactly of positions whose outcome is not certified as a finite forced win or finite forced loss by this propagation.Uis not used as a supervised target in the clean experiment.

The supervised object is not the full descendant game graph, but a canonical proof trace for the root value. We fix an order on legal moves. AWinstate is certified by recursively proving the firstLosechild in that order. ALosestate is certified by recursively proving all legal children, each of which must beWin. We keep a root only when this canonical trace is finite and every state queried by the trace has valueWinorLose. This is a proof-trace filter rather than a full-subtree filter: a keptWinroot may have unqueried moves leading toU, while a keptLoseroot must certify all legal children.

For each kept root, CoT, PENCIL, and the recursive model are trained on different renderings of this same canonical trace. CoT linearizes the depth-first proof into one flat transcript. PENCIL keeps one running context, but compresses completed subproofs to their returnedWin/Losevalues. The recursive rendering places each subproof in its owncall/returnframe; after a child returns, the parent receives only the child value. Thus the methods share the same roots, values, and proof supervision, and differ only in how much of the proof history remains visible. During training, inserted return values may appear as context after a subproof completes, but the loss is applied only to the local continuation tokens generated in the active rendering. At evaluation time, return values are generated by the model; the exact value table is used only for scoring.

C.2Data Splits

The IID Go split contains 90K root positions: 80K roots for training and 10K held-out roots for evaluation. The table in the main text reports the final checkpoint after 64K training updates. IID trace accuracy is computed on the first 1K held-out roots, and IID rollout end-to-end accuracy is computed on 256 held-out roots.

For the context-efficiency statistic in the main text, we use all 10K IID held-out roots. Active context length is the maximum number of tokens visible to any next-token prediction within a trace: the causal prefix for CoT, the current single-context state for PENCIL, and the active frame for the recursive model.

We also construct a length-OOD diagnostic split by sorting roots by the length of their flat CoT trace and training on the shortest 80K roots while evaluating on the longest 20K roots. The main table reports length-OOD trace accuracy on the first 1K held-out roots from this split. The rollout final-label metrics in the main text are evaluated separately on 256 IID held-out roots, matching the IID rollout protocol above. This split is harder because test proofs require much longer searches: flat CoT traces average 677 tokens in training and 6,956 tokens in testing, while recursive traces average 997 total tokens over 34.6 frames in training and 9,876 total tokens over 316.4 frames in testing.

C.3Model and Optimization

All Go methods use the same decoder-only Transformer trained from scratch. The model has 4 layers, 4 attention heads, hidden width 256, RoPE positional embeddings, vocabulary size 104, and 3,176,960 parameters.

We train CoT, PENCIL, and Recursive Model checkpoints for 64K updates with AdamW, weight decay 0.1, gradient clipping at 1.0, and bfloat16 training. The learning rate is3×10−43\times 10^{-4}for the first 32K updates and3×10−53\times 10^{-5}for updates 32K–64K, with no warmup and no cosine decay. CoT uses ordinary causal attention; PENCIL and the recursive model use attention masks matching their visible contexts.

C.4Evaluation Metrics

We report trace accuracy and two rollout final-label metrics.Trace accuracyis a teacher-forced exact-match metric over the full canonical solver trace: a held-out root is counted correct only if every supervised token in the rendered trace is predicted correctly from the gold visible context. This is the primary metric for measuring whether the model learned the solver trajectory.

True end-to-end accuracyis computed by autoregressively rolling out the trained model and checking only whether the final rootWin/Loseanswer matches the exact solver label.Strict end-to-end accuracyadditionally requires the generated rollout to parse as a legal and consistent solver trace before the final answer is counted. Concretely, every generated call must contain a parseable child board, the precedingTRYmove must be legal from the current board, the emitted child board must equal the board obtained by applying that move, and the rollout must return a parseable root label. True end-to-end accuracy is useful as an outcome measure, but is less diagnostic because the final binary label can be easier than reproducing the full solver trace.

Appendix DTransformer Architecture

We define the decoder-only Transformer architecture used throughout this paper. LetΣ\Sigmabe a finite vocabulary andddbe the hidden dimension.

Token and Positional Embeddings.

Atoken embedding𝖳𝖤:Σ→ℝd\mathsf{TE}:\Sigma\to\mathbb{R}^{d}maps each token to add-dimensional vector. Apositional embedding𝖯𝖤:ℕ+→ℝd\mathsf{PE}:\mathbb{N}^{+}\to\mathbb{R}^{d}encodes position information. For an input sequence(x1,…,xn)∈Σn(x_{1},\ldots,x_{n})\in\Sigma^{n}, the initial embedding at positioniiishi(0)=𝖳𝖤​(xi)+𝖯𝖤​(i)h_{i}^{(0)}=\mathsf{TE}(x_{i})+\mathsf{PE}(i).

Attention.

For query, key, and value vectors(q,kj,vj)j=1n(q,k_{j},v_{j})_{j=1}^{n}whereq,kj∈ℝdkq,k_{j}\in\mathbb{R}^{d_{k}}andvj∈ℝdvv_{j}\in\mathbb{R}^{d_{v}}, the attention output with temperatureβ>0\beta>0is:

𝖠𝗍𝗍𝗇β​(q,{kj,vj}j=1n)=∑j=1nαj​vj,where​α=softmaxβ​((q⋅kj)j=1n),\mathsf{Attn}_{\beta}(q,\{k_{j},v_{j}\}_{j=1}^{n})=\sum_{j=1}^{n}\alpha_{j}v_{j},\quad\text{where }\alpha=\mathrm{softmax}_{\beta}\left((q\cdot k_{j})_{j=1}^{n}\right),(13)and[softmaxβ​(z)]i=exp⁡(zi/β)/∑jexp⁡(zj/β)[\mathrm{softmax}_{\beta}(z)]_{i}=\exp(z_{i}/\beta)/\sum_{j}\exp(z_{j}/\beta).

Average-Hard Attention (AHA).

Taking the zero-temperature limitβ→0\beta\to 0yields average-hard attention(Merrill et al.,2022), which uniformly averages over the maximum-scoring positions:

𝖠𝖧𝖠​(q,{kj,vj}j=1n)=1|A|​∑j∈Avj,where​A=arg⁡maxj∈[n]⁡⟨q,kj⟩.\mathsf{AHA}(q,\{k_{j},v_{j}\}_{j=1}^{n})=\frac{1}{|A|}\sum_{j\in A}v_{j},\quad\text{where }A=\arg\max_{j\in[n]}\langle q,k_{j}\rangle.(14)AHA involves only comparisons and uniform averaging, which can be computed exactly in finite precision. All theoretical results in this paper use AHA.

Multi-Head Self-Attention.

Amulti-head self-attentionlayer withHHheads is parametrized by projection matricesWQh,WKh,WVh∈ℝdk×dW_{Q}^{h},W_{K}^{h},W_{V}^{h}\in\mathbb{R}^{d_{k}\times d}andWOh∈ℝd×dkW_{O}^{h}\in\mathbb{R}^{d\times d_{k}}forh∈[H]h\in[H]. For embeddings(h1,…,hn)(h_{1},\ldots,h_{n}), the output at positionnnis:

𝖬𝖧𝖠​(h1,…,hn)=∑h=1HWOh⋅𝖠𝖧𝖠​(WQh​hn,{WKh​hj,WVh​hj}j=1n).\mathsf{MHA}(h_{1},\ldots,h_{n})=\sum_{h=1}^{H}W_{O}^{h}\cdot\mathsf{AHA}\left(W_{Q}^{h}h_{n},\{W_{K}^{h}h_{j},W_{V}^{h}h_{j}\}_{j=1}^{n}\right).(15)For decoder-only (causal) Transformers, positionnnattends only to positionsj≤nj\leq n.

Feed-Forward Layer.

Afeed-forwardlayer with widthd𝖿𝖿d_{\mathsf{ff}}and activationσ\sigmais defined as:

𝖥𝖥​(h)=W2⋅σ​(W1⋅h+b1)+b2,\mathsf{FF}(h)=W_{2}\cdot\sigma(W_{1}\cdot h+b_{1})+b_{2},(16)whereW1∈ℝd𝖿𝖿×dW_{1}\in\mathbb{R}^{d_{\mathsf{ff}}\times d},W2∈ℝd×d𝖿𝖿W_{2}\in\mathbb{R}^{d\times d_{\mathsf{ff}}}, andb1,b2b_{1},b_{2}are bias terms.

Transformer Layer.

A singleTransformer layercombines multi-head attention and feed-forward with residual connections:

𝖳𝖥​(h1,…,hn)=𝖥𝖥​(h~n)+h~n,where​h~n=𝖬𝖧𝖠​(h1,…,hn)+hn.\mathsf{TF}(h_{1},\ldots,h_{n})=\mathsf{FF}(\tilde{h}_{n})+\tilde{h}_{n},\quad\text{where }\tilde{h}_{n}=\mathsf{MHA}(h_{1},\ldots,h_{n})+h_{n}.(17)

Next-Token Predictor.

AnLL-layer decoder-only Transformer defines a next-token predictorfθ:Σ∗→Σf_{\theta}:\Sigma^{*}\to\Sigmaas:

fθ(x1,…,xn)=argmaxx∈Σ[W𝖽𝖾𝖼⋅hn(L)]x,f_{\theta}(x_{1},\ldots,x_{n})=\arg\max_{x\in\Sigma}\left[W_{\mathsf{dec}}\cdot h_{n}^{(L)}\right]_{x},(18)wherehn(L)h_{n}^{(L)}is the final-layer embedding at positionnn, computed by stackingLLTransformer layers on top of the initial embeddings, andW𝖽𝖾𝖼∈ℝ|Σ|×dW_{\mathsf{dec}}\in\mathbb{R}^{|\Sigma|\times d}is the decoding matrix.

Precision.

We say a Transformer has𝒪​(log⁡S​(n))\mathcal{O}(\log S(n))precisionif all intermediate numerical values (embeddings, attention scores, and feed-forward activations) are rational numbersp/qp/qwith|p|,|q|≤S​(n)C|p|,|q|\leq S(n)^{C}for a universal constantCC, whereS​(n)S(n)is the local space bound, i.e., the input sequence length to the Transformer. Equivalently, each value is representable in𝒪​(log⁡S​(n))\mathcal{O}(\log S(n))bits, and all arithmetic is exact with no rounding. This precision model is consistent withYang et al. (2025a): operations such asseq_sumoverS​(n)S(n)indicator values produce results bounded byS​(n)S(n),seq_maxpreserves input magnitudes, andrightmost_exact_matchconcentrates attention on a single position, all within𝒪​(log⁡S​(n))\mathcal{O}(\log S(n))-bit exact arithmetic.

Appendix ESingle-Tape Turing Machine

A single-tape Turing machine operates on an infinite tape indexed byℤ\mathbb{Z}, where each cell holds a symbol from a finite tape alphabetΓ\Gamma. A read/write head moves along the tape, and a finite set of control states governs the machine’s behavior. Formally, a Turing machine is a 7-tuple𝖳𝖬=(Γ,b,Q,q0,δ,Qacc,Qrej)\mathsf{TM}=(\Gamma,b,Q,q_{0},\delta,Q_{\mathrm{acc}},Q_{\mathrm{rej}}), whereb∈Γb\in\Gammais the blank symbol;q0∈Qq_{0}\in Qis the initial state;δ:(Q∖(Qacc∪Qrej))×Γ→Q×Γ×{−1,0,+1}\delta:(Q\setminus(Q_{\mathrm{acc}}\cup Q_{\mathrm{rej}}))\times\Gamma\to Q\times\Gamma\times\{-1,0,+1\}is the transition function; andQacc,Qrej⊆QQ_{\mathrm{acc}},Q_{\mathrm{rej}}\subseteq Qare disjoint accepting and rejecting states.

Execution.

Given inputx∈(Γ∖{b})nx\in(\Gamma\setminus\{b\})^{n}, the tape is initialized withxxin cells0,…,n−10,\ldots,n-1and blanks elsewhere; the head starts at position0in stateq0q_{0}. At each step, the machine reads the symbolaaunder the head, computes(q′,w,d)=δ​(q,a)(q^{\prime},w,d)=\delta(q,a), writesww, moves the head byd∈{−1,0,+1}d\in\{-1,0,+1\}, and transitions to stateq′q^{\prime}. The machine halts upon enteringQacc∪QrejQ_{\mathrm{acc}}\cup Q_{\mathrm{rej}}, outputting11(accept) or0(reject) accordingly.

Normalization.

To ensure configurations are well-defined for allt≤T​(n)t\leq T(n), we extendδ\deltato halting states by making them self-loops: for allq∈Qacc∪Qrejq\in Q_{\mathrm{acc}}\cup Q_{\mathrm{rej}}anda∈Γa\in\Gamma, defineδ​(q,a):=(q,a,0)\delta(q,a):=(q,a,0). This does not change the language decided by𝖳𝖬\mathsf{TM}.

Complexity Classes.

Thetime complexityT​(𝖳𝖬,x)T(\mathsf{TM},x)is the number of steps before halting. Thespace complexityS​(𝖳𝖬,x)S(\mathsf{TM},x)is the number of distinct tape cells visited. A Turing machine𝖳𝖬\mathsf{TM}decidesa languageL⊆Σ∗L\subseteq\Sigma^{*}if it halts on all inputs and accepts exactly those inLL. The complexity classes are defined as:

𝖳𝖨𝖬𝖤​(f​(n))\displaystyle\mathsf{TIME}(f(n))={L:∃𝖳𝖬​deciding​L​with​T​(𝖳𝖬,x)≤f​(|x|)​for all​x},\displaystyle=\{L:\exists\,\mathsf{TM}\text{ deciding }L\text{ with }T(\mathsf{TM},x)\leq f(|x|)\text{ for all }x\},(19)𝖲𝖯𝖠𝖢𝖤​(f​(n))\displaystyle\mathsf{SPACE}(f(n))={L:∃𝖳𝖬​deciding​L​with​S​(𝖳𝖬,x)≤f​(|x|)​for all​x}.\displaystyle=\{L:\exists\,\mathsf{TM}\text{ deciding }L\text{ with }S(\mathsf{TM},x)\leq f(|x|)\text{ for all }x\}.(20)We write𝖳𝖬​(s​(n),t​(n))\mathsf{TM}(s(n),t(n))for the simultaneous space-time class: languages decided by a single deterministic Turing machine whose space and time on every inputxxare at most𝒪​(s​(|x|))\mathcal{O}(s(|x|))and𝒪​(t​(|x|))\mathcal{O}(t(|x|)), respectively.

Appendix FProof of Theorem1

Theorem 6(Deep Recursive Models, Formal).

For anyS​(n)≥nS(n)\geq n, recursive models can solve any problem in𝖳𝖨𝖬𝖤​(2𝒪​(S​(n)))\mathsf{TIME}(2^{\mathcal{O}(S(n))})under local space constraint𝒪​(S​(n))\mathcal{O}(S(n)):

𝖳𝖨𝖬𝖤​(2𝒪​(S​(n)))⊆𝖱𝖬​(𝒪​(S​(n)),∞,∞).\mathsf{TIME}(2^{\mathcal{O}(S(n))})\subseteq\mathsf{RM}(\mathcal{O}(S(n)),\infty,\infty).(21)

The proof proceeds in two parts:(1)we define mutually recursive functions that compute TM configurations and prove their correctness;(2)we analyze the resource consumption (local space, recursion depth, and runtime). We further provides a sketch for constructing the Transformer but the detailed implementation is omitted. An alternative proof via Alternating Turing Machines appears in AppendixG, which includes the detailed implementation for the corresponding Transformer.

F.1Recursive Construction

Let𝖳𝖬=(Γ,b,Q,q0,δ,Qacc,Qrej)\mathsf{TM}=(\Gamma,b,Q,q_{0},\delta,Q_{\mathrm{acc}},Q_{\mathrm{rej}})be a single-tape Turing machine. We use timettto denote the number of transitions already executed:t=0t=0is the initial configuration, and transitioning fromtttot+1t+1executes thett-th transition.

Configuration.

Aconfigurationof𝖳𝖬\mathsf{TM}at timettis a triplect=(qt,τt,pt)c_{t}=(q_{t},\tau_{t},p_{t})where:

• •qt∈Qq_{t}\in Qis the control state at timett;
• •τt:ℤ→Γ\tau_{t}:\mathbb{Z}\to\Gammais thetape contentsat timett, mapping each cell index to a symbol, withτt​(i)=b\tau_{t}(i)=b(the blank symbol) for all but finitely manyii;
• •pt∈ℤp_{t}\in\mathbb{Z}is the head position at timett.

For a tapeτ\tauand positionpp, we writeτ​[p↦w]\tau[p\mapsto w]for the tape that agrees withτ\taueverywhere except at positionpp, where it holds symbolww. The initial configuration isc0=(q0,τ0,0)c_{0}=(q_{0},\tau_{0},0)whereτ0​(i)=x​[i]\tau_{0}(i)=x[i]for0≤i<n0\leq i<nandτ0​(i)=b\tau_{0}(i)=botherwise.

Recursive functions.

We define the following mutually recursive functions that compute the components ofctc_{t}. Letx∈(Γ∖{b})nx\in(\Gamma\setminus\{b\})^{n}be the input.

• •𝖲𝖳𝖠𝖳𝖤​(x,t)∈Q\mathsf{STATE}(x,t)\in Q: returns the control stateqtq_{t}
• •𝖯𝖮𝖲​(x,t)∈ℤ\mathsf{POS}(x,t)\in\mathbb{Z}: returns the head positionptp_{t}
• •𝖢𝖤𝖫𝖫​(x,t,p)∈Γ\mathsf{CELL}(x,t,p)\in\Gamma: returns the tape symbolτt​(p)\tau_{t}(p)at positionpp
• •𝖲𝖸𝖬𝖡𝖮𝖫​(x,t)∈Γ\mathsf{SYMBOL}(x,t)\in\Gamma: returns the symbol under the headτt​(pt)\tau_{t}(p_{t})
• •𝖱𝖴𝖭​(x,t)∈{0,1}\mathsf{RUN}(x,t)\in\{0,1\}: starting from timett, simulate until halting and return accept (1) or reject (0)

Algorithm.

The following five algorithms present the pseudocode for these mutually recursive functions. The transition functionδ\deltais assumed to be hardcoded into the model parameters. We fix a constantc>0c>0such that the Turing machine𝖳𝖬\mathsf{TM}decidingLLhalts withinT​(n):=2c⋅S​(n)T(n):=2^{c\cdot S(n)}steps on all inputs of lengthnn.

Algorithm 6𝖲𝖳𝖠𝖳𝖤​(x,t)→qt∈Q\mathsf{STATE}(x,t)\to q_{t}\in Q1:if

t=0t=0then return

q0q_{0} 2:

(q′,w,d)←δ​(𝖲𝖳𝖠𝖳𝖤​(x,t−1),𝖲𝖸𝖬𝖡𝖮𝖫​(x,t−1))(q^{\prime},w,d)\leftarrow\delta(\mathsf{STATE}(x,t-1),\mathsf{SYMBOL}(x,t-1)) 3:return

q′q^{\prime}

Algorithm 7𝖯𝖮𝖲​(x,t)→pt∈ℤ\mathsf{POS}(x,t)\to p_{t}\in\mathbb{Z}1:if

t=0t=0then return

0 2:

(q′,w,d)←δ​(𝖲𝖳𝖠𝖳𝖤​(x,t−1),𝖲𝖸𝖬𝖡𝖮𝖫​(x,t−1))(q^{\prime},w,d)\leftarrow\delta(\mathsf{STATE}(x,t-1),\mathsf{SYMBOL}(x,t-1)) 3:return

𝖯𝖮𝖲​(x,t−1)+d\mathsf{POS}(x,t-1)+d

Algorithm 8𝖢𝖤𝖫𝖫​(x,t,p)→τt​(p)∈Γ\mathsf{CELL}(x,t,p)\to\tau_{t}(p)\in\Gamma1:if

t=0t=0then return

x​[p]x[p]if

0≤p<|x|0\leq p<|x|else

bb 2:

pprev←𝖯𝖮𝖲​(x,t−1)p_{\mathrm{prev}}\leftarrow\mathsf{POS}(x,t-1) 3:if

p≠pprevp\neq p_{\mathrm{prev}}then return

𝖢𝖤𝖫𝖫​(x,t−1,p)\mathsf{CELL}(x,t-1,p)⊳\trianglerightrecurse

4:

(q′,w,d)←δ​(𝖲𝖳𝖠𝖳𝖤​(x,t−1),𝖲𝖸𝖬𝖡𝖮𝖫​(x,t−1))(q^{\prime},w,d)\leftarrow\delta(\mathsf{STATE}(x,t-1),\mathsf{SYMBOL}(x,t-1)) 5:return

ww⊳\trianglerightsymbol written att−1t-1

Algorithm 9𝖲𝖸𝖬𝖡𝖮𝖫​(x,t)→τt​(pt)∈Γ\mathsf{SYMBOL}(x,t)\to\tau_{t}(p_{t})\in\Gamma1:return

𝖢𝖤𝖫𝖫​(x,t,𝖯𝖮𝖲​(x,t))\mathsf{CELL}(x,t,\mathsf{POS}(x,t)) Algorithm 10𝖱𝖴𝖭​(x,t)→{0,1}\mathsf{RUN}(x,t)\to\{0,1\}1:

q←𝖲𝖳𝖠𝖳𝖤​(x,t)q\leftarrow\mathsf{STATE}(x,t) 2:if

q∈Qaccq\in Q_{\mathrm{acc}}then return

11⊳\trianglerightaccept

3:if

q∈Qrejq\in Q_{\mathrm{rej}}then return

0⊳\trianglerightreject

4:return

𝖱𝖴𝖭​(x,t+1)\mathsf{RUN}(x,t+1)⊳\trianglerightcontinue

The decision procedure is𝖣𝖤𝖢𝖨𝖣𝖤​(x):=𝖱𝖴𝖭​(x,0)\mathsf{DECIDE}(x):=\mathsf{RUN}(x,0). SinceL∈𝖳𝖨𝖬𝖤​(2𝒪​(S​(n)))L\in\mathsf{TIME}(2^{\mathcal{O}(S(n))}), the TM halts withinT=2c⋅S​(n)T=2^{c\cdot S(n)}steps, so𝖱𝖴𝖭\mathsf{RUN}terminates and correctly outputs accept/reject. We now show that the recursive semantics faithfully tracks the TM’s behavior.

Lemma 7(Correctness of Recursive Semantics).

Letqt,pt,τtq_{t},p_{t},\tau_{t}denote the true state, head position, and tape contents of𝖳𝖬\mathsf{TM}at timett. For every inputxx, everyt≥0t\geq 0, and every positionp∈ℤp\in\mathbb{Z}:

1. 1.𝖲𝖳𝖠𝖳𝖤​(x,t)=qt\mathsf{STATE}(x,t)=q_{t}
2. 2.𝖯𝖮𝖲​(x,t)=pt\mathsf{POS}(x,t)=p_{t}
3. 3.𝖢𝖤𝖫𝖫​(x,t,p)=τt​(p)\mathsf{CELL}(x,t,p)=\tau_{t}(p)
4. 4.𝖲𝖸𝖬𝖡𝖮𝖫​(x,t)=τt​(pt)\mathsf{SYMBOL}(x,t)=\tau_{t}(p_{t})

Proof.

By induction ontt.

*Base case (t=0t=0):*By the TM initialization semantics,q0q_{0}is the initial state,p0=0p_{0}=0, andτ0​(p)=x​[p]\tau_{0}(p)=x[p]for0≤p<n0\leq p<nandτ0​(p)=b\tau_{0}(p)=botherwise. These match the base cases of our recursive functions. For claim (4),𝖲𝖸𝖬𝖡𝖮𝖫​(x,0)=𝖢𝖤𝖫𝖫​(x,0,𝖯𝖮𝖲​(x,0))=τ0​(0)=τ0​(p0)\mathsf{SYMBOL}(x,0)=\mathsf{CELL}(x,0,\mathsf{POS}(x,0))=\tau_{0}(0)=\tau_{0}(p_{0}).

*Inductive step (t≥1t\geq 1):*Assume the claims hold for timet−1t-1. By definition and the induction hypothesis:

𝖲𝖸𝖬𝖡𝖮𝖫​(x,t−1)=𝖢𝖤𝖫𝖫​(x,t−1,𝖯𝖮𝖲​(x,t−1))=τt−1​(pt−1)\mathsf{SYMBOL}(x,t-1)=\mathsf{CELL}(x,t-1,\mathsf{POS}(x,t-1))=\tau_{t-1}(p_{t-1})(22) Let(q′,w,d):=δ​(𝖲𝖳𝖠𝖳𝖤​(x,t−1),𝖲𝖸𝖬𝖡𝖮𝖫​(x,t−1))(q^{\prime},w,d):=\delta(\mathsf{STATE}(x,t-1),\mathsf{SYMBOL}(x,t-1))be the transition output. By the induction hypothesis,𝖲𝖳𝖠𝖳𝖤​(x,t−1)=qt−1\mathsf{STATE}(x,t-1)=q_{t-1}, so the transitionδ​(qt−1,τt−1​(pt−1))\delta(q_{t-1},\tau_{t-1}(p_{t-1}))computed by the algorithm is exactly the transition taken by𝖳𝖬\mathsf{TM}at stept−1t-1. Thus:

• •𝖲𝖳𝖠𝖳𝖤​(x,t)=q′=qt\mathsf{STATE}(x,t)=q^{\prime}=q_{t}(the new state fromδ\delta)
• •𝖯𝖮𝖲​(x,t)=pt−1+d=pt\mathsf{POS}(x,t)=p_{t-1}+d=p_{t}(head moves bydd)
• •𝖢𝖤𝖫𝖫​(x,t,p)=τt​(p)\mathsf{CELL}(x,t,p)=\tau_{t}(p): only cellpt−1p_{t-1}changes toww; others unchanged
• •𝖲𝖸𝖬𝖡𝖮𝖫​(x,t)=𝖢𝖤𝖫𝖫​(x,t,𝖯𝖮𝖲​(x,t))=τt​(pt)\mathsf{SYMBOL}(x,t)=\mathsf{CELL}(x,t,\mathsf{POS}(x,t))=\tau_{t}(p_{t})

This completes the induction. ∎

F.2Resource Analysis

We analyze three resources: local space (per-context length), recursion depth (call stack height), and total runtime (number of recursive calls).

Local Space.

Each recursive frame must store the following data:

• •Inputxx: lengthnn
• •Time parametert′t^{\prime}:O​(log⁡t)O(\log t)bits in binary representation
• •Position parameterpp(for𝖢𝖤𝖫𝖫\mathsf{CELL}): since the head moves at most 1 cell per step,|p|≤t|p|\leq t, so|bin​(p)|=O​(log⁡t)|\mathrm{bin}(p)|=O(\log t)
• •Stateq∈Qq\in Q,symbola∈Γa\in\Gamma,move directiond∈{−1,0,+1}d\in\{-1,0,+1\}:O​(1)O(1)bits (finite sets)
• •Returned answers from subcalls: state (O​(1)O(1)), position (O​(log⁡t)O(\log t)), symbol (O​(1)O(1))

Crucially, each context makes onlyO​(1)O(1)nested calls before returning. When a callee returns, the call/return mechanism removes its entire context from the stack and appends only the returned value to the caller’s context. This prevents accumulation of intermediate results. Thus, each context has lengthO​(n+log⁡t)O(n+\log t). In Theorem6,t≤T​(n)=2c⋅S​(n)t\leq T(n)=2^{c\cdot S(n)}, solog⁡t≤c⋅S​(n)\log t\leq c\cdot S(n). SinceS​(n)≥nS(n)\geq n, the local space bound isO​(n+S​(n))=O​(S​(n))O(n+S(n))=O(S(n)). Moreover, the complete rollout before each call or return adds only a constant number of delimiters and a subcall prompt or returned value of lengthO​(n+log⁡t)O(n+\log t), so the transient rollout stack also has local spaceO​(S​(n))O(S(n)).

Recursion Depth.

For the inner functions (𝖲𝖳𝖠𝖳𝖤,𝖯𝖮𝖲,𝖢𝖤𝖫𝖫,𝖲𝖸𝖬𝖡𝖮𝖫\mathsf{STATE},\mathsf{POS},\mathsf{CELL},\mathsf{SYMBOL}): each call with time parameterttrecursively invokes only subcalls with parametert−1t-1. Thus, starting fromt=T​(n)t=T(n), the recursion depth isO​(T​(n))O(T(n)).

For the outer decision procedure𝖱𝖴𝖭\mathsf{RUN}: even without assuming any tail-call optimization, the additional stack height contributed by iterating through time steps0,1,…0,1,\ldotsis at mostO​(T​(n))O(T(n)). Each𝖱𝖴𝖭​(x,t)\mathsf{RUN}(x,t)calls𝖲𝖳𝖠𝖳𝖤​(x,t)\mathsf{STATE}(x,t), which itself has depthO​(t)O(t).

Overall, the maximum recursion depth isO​(T​(n))=O​(2c⋅S​(n))O(T(n))=O(2^{c\cdot S(n)}).

Time Complexity (Total Subroutine Invocations).

We measure runtime by the total number of subroutine invocations across all recursive contexts. Since the Transformerfθf_{\theta}has constant size and each invocation produces at mostO​(S​(n))O(S(n))tokens, this differs from the total token count by at most anO​(S​(n))O(S(n))factor.

For each routine𝖥∈{𝖲𝖳𝖠𝖳𝖤,𝖯𝖮𝖲,𝖢𝖤𝖫𝖫,𝖲𝖸𝖬𝖡𝖮𝖫,𝖱𝖴𝖭}\mathsf{F}\in\{\mathsf{STATE},\mathsf{POS},\mathsf{CELL},\mathsf{SYMBOL},\mathsf{RUN}\}, let𝒯𝖥​(t)\mathcal{T}_{\mathsf{F}}(t)denote the worst-case total number of subroutine invocations triggered by evaluating𝖥​(x,t)\mathsf{F}(x,t)(for𝖢𝖤𝖫𝖫\mathsf{CELL}, we also maximize overp∈ℤp\in\mathbb{Z}). From Algorithms 1–5:

𝒯𝖲𝖳𝖠𝖳𝖤​(t)\displaystyle\mathcal{T}_{\mathsf{STATE}}(t)≤𝒯𝖲𝖳𝖠𝖳𝖤​(t−1)+𝒯𝖲𝖸𝖬𝖡𝖮𝖫​(t−1)+O​(1),\displaystyle\leq\mathcal{T}_{\mathsf{STATE}}(t-1)+\mathcal{T}_{\mathsf{SYMBOL}}(t-1)+O(1),(23)𝒯𝖯𝖮𝖲​(t)\displaystyle\mathcal{T}_{\mathsf{POS}}(t)≤𝒯𝖯𝖮𝖲​(t−1)+𝒯𝖲𝖳𝖠𝖳𝖤​(t−1)+𝒯𝖲𝖸𝖬𝖡𝖮𝖫​(t−1)+O​(1),\displaystyle\leq\mathcal{T}_{\mathsf{POS}}(t-1)+\mathcal{T}_{\mathsf{STATE}}(t-1)+\mathcal{T}_{\mathsf{SYMBOL}}(t-1)+O(1),(24)𝒯𝖢𝖤𝖫𝖫​(t)\displaystyle\mathcal{T}_{\mathsf{CELL}}(t)≤𝒯𝖯𝖮𝖲​(t−1)+max⁡{𝒯𝖢𝖤𝖫𝖫​(t−1),𝒯𝖲𝖳𝖠𝖳𝖤​(t−1)+𝒯𝖲𝖸𝖬𝖡𝖮𝖫​(t−1)}+O​(1),\displaystyle\leq\mathcal{T}_{\mathsf{POS}}(t-1)+\max\!\big\{\mathcal{T}_{\mathsf{CELL}}(t-1),\,\mathcal{T}_{\mathsf{STATE}}(t-1)+\mathcal{T}_{\mathsf{SYMBOL}}(t-1)\big\}+O(1),(25)𝒯𝖲𝖸𝖬𝖡𝖮𝖫​(t)\displaystyle\mathcal{T}_{\mathsf{SYMBOL}}(t)≤𝒯𝖯𝖮𝖲​(t)+𝒯𝖢𝖤𝖫𝖫​(t)+O​(1),\displaystyle\leq\mathcal{T}_{\mathsf{POS}}(t)+\mathcal{T}_{\mathsf{CELL}}(t)+O(1),(26)𝒯𝖱𝖴𝖭​(t)\displaystyle\mathcal{T}_{\mathsf{RUN}}(t)≤𝒯𝖲𝖳𝖠𝖳𝖤​(t)+𝒯𝖱𝖴𝖭​(t+1)+O​(1).\displaystyle\leq\mathcal{T}_{\mathsf{STATE}}(t)+\mathcal{T}_{\mathsf{RUN}}(t+1)+O(1).(27) To simplify these coupled recurrences, we define two dominant quantities:

V​(t):=max⁡{𝒯𝖲𝖳𝖠𝖳𝖤​(t),𝒯𝖯𝖮𝖲​(t)},C​(t):=𝒯𝖢𝖤𝖫𝖫​(t).V(t):=\max\big\{\mathcal{T}_{\mathsf{STATE}}(t),\,\mathcal{T}_{\mathsf{POS}}(t)\big\},\qquad C(t):=\mathcal{T}_{\mathsf{CELL}}(t).(28)By equation26,𝒯𝖲𝖸𝖬𝖡𝖮𝖫​(t)≤V​(t)+C​(t)+O​(1)\mathcal{T}_{\mathsf{SYMBOL}}(t)\leq V(t)+C(t)+O(1). Substituting into equation23–equation25yields:

V​(t)\displaystyle V(t)≤3​V​(t−1)+C​(t−1)+O​(1),\displaystyle\leq 3V(t-1)+C(t-1)+O(1),C​(t)\displaystyle C(t)≤3​V​(t−1)+C​(t−1)+O​(1).\displaystyle\leq 3V(t-1)+C(t-1)+O(1).Therefore,

(V​(t)C​(t))⪯(3131)​(V​(t−1)C​(t−1))+O​(1),\begin{pmatrix}V(t)\\ C(t)\end{pmatrix}\preceq\begin{pmatrix}3&1\\ 3&1\end{pmatrix}\begin{pmatrix}V(t-1)\\ C(t-1)\end{pmatrix}+O(1),(29)whose spectral radius is44. HenceV​(t),C​(t)=O​(4t)V(t),C(t)=O(4^{t}).

Finally, if the simulated Turing machine halts withinT​(n)T(n)steps, then𝖱𝖴𝖭​(x,0)\mathsf{RUN}(x,0)performs at mostT​(n)T(n)iterations, each invoking𝖲𝖳𝖠𝖳𝖤​(x,t)\mathsf{STATE}(x,t)once. Using equation27:

𝒯𝖱𝖴𝖭​(0)≤∑t=0T​(n)𝒯𝖲𝖳𝖠𝖳𝖤​(t)=O​(V​(T​(n)))=O​(4T​(n)).\mathcal{T}_{\mathsf{RUN}}(0)\leq\sum_{t=0}^{T(n)}\mathcal{T}_{\mathsf{STATE}}(t)=O(V(T(n)))=O(4^{T(n)}).(30)ForT​(n)=2c⋅S​(n)T(n)=2^{c\cdot S(n)}, this becomes4T​(n)=22​T​(n)=22Θ​(S​(n))4^{T(n)}=2^{2T(n)}=2^{2^{\Theta(S(n))}}, i.e., double exponential inS​(n)S(n). Since each invocation produces at mostO​(S​(n))O(S(n))tokens, the total generated tokens remain22Θ​(S​(n))2^{2^{\Theta(S(n))}}.

This double-exponential runtime doesnotaffect the𝖱𝖬​(⋅,⋅)\mathsf{RM}(\cdot,\cdot)membership statement, which constrains only local space and recursion depth. To reduce runtime to2𝒪​(S​(n))2^{\mathcal{O}(S(n))}, one can augment the simulation with memoization: caching results of𝖲𝖳𝖠𝖳𝖤​(x,t′)\mathsf{STATE}(x,t^{\prime})in external storage ensures each subproblem is computed only once.

F.3Transformer Construction

We sketch how a Transformer can implement the recursive simulation described above. The key insight is that each step of Algorithms 1–5 involves only: (i) parsing a bounded-length prefix to identify the function and arguments, (ii) counting delimiters to determine the current phase, (iii) performing constant-size table lookups (δ\delta,QaccQ_{\mathrm{acc}},QrejQ_{\mathrm{rej}}), and (iv) emitting tokens for calls/returns.

F.3.1Setup

Token Vocabulary.

We define the following special tokens:

• •Function tokens:⟨STATE⟩\langle\texttt{STATE}\rangle,⟨POS⟩\langle\texttt{POS}\rangle,⟨CELL⟩\langle\texttt{CELL}\rangle,⟨SYMBOL⟩\langle\texttt{SYMBOL}\rangle,⟨RUN⟩\langle\texttt{RUN}\rangleindicate which recursive function is being invoked.
• •Control tokens:⟨call⟩\langle\texttt{call}\rangle,⟨/call⟩\langle/\texttt{call}\rangle,⟨return⟩\langle\texttt{return}\rangle,⟨/return⟩\langle/\texttt{return}\ranglemark the boundaries of recursive calls and returns.
• •Separator tokens:⟨sep⟩\langle\texttt{sep}\rangleseparates arguments within a call;[SEP]is an internal delimiter that separates cached intermediate results within a context.
• •Data tokens: Tokens fromΓ\Gamma(tape alphabet),QQ(states), and binary digits{0,1}\{0,1\}for encoding integers.

Context Format.

Each function-call frame is a single sequence (context) whose prefix contains the input arguments, and whose suffix progressively caches intermediate results from subcalls. A typical context has the form:

⟨F⟩​⟨sep⟩​arg1​⟨sep⟩​arg2​(⟨sep⟩​arg3)​[SEP]​z1​[SEP]​z2​⋯\langle F\rangle\;\langle\texttt{sep}\rangle\;\text{arg}_{1}\;\langle\texttt{sep}\rangle\;\text{arg}_{2}\;\big(\;\langle\texttt{sep}\rangle\;\text{arg}_{3}\;\big)\;\;\texttt{[SEP]}\;z_{1}\;\texttt{[SEP]}\;z_{2}\;\cdots(31)where⟨F⟩\langle F\rangleis the function token (e.g.,⟨STATE⟩\langle\texttt{STATE}\rangle), and eachziz_{i}is either a returned value from a recursive call or an internally produced constant-size token. Recursive calls are wrapped as⟨call⟩⟨F⟩⟨sep⟩⋯⟨/call⟩\langle\texttt{call}\rangle\langle F\rangle\langle\texttt{sep}\rangle\cdots\langle/\texttt{call}\rangle. Returns are encoded as⟨return⟩[SEP]∥𝐯⟨/return⟩\langle\texttt{return}\rangle\texttt{[SEP]}\mathbin{\|}\mathbf{v}\langle/\texttt{return}\rangle—note that the payload begins with[SEP]. Thus, when a subcall finishes, the caller receives the payload[SEP]∥𝐯\texttt{[SEP]}\mathbin{\|}\mathbf{v}appended to its context, so each completed subcall contributes exactly one[SEP]delimiter to the caller’s phase cache.

Transformer Behavior.

The Transformerfθf_{\theta}decides what to do next by inspecting only: (i) which function token⟨F⟩\langle F\ranglebegins the context, (ii) whether the time argument is zero (via a bit-scan), and (iii) how many[SEP]delimiters have already appeared (the “phase”). This is a standard finite-phase construction: each function needs only a constant number of phases to implement the corresponding algorithmic step. Specifically,fθf_{\theta}executes the logic specified in Algorithms 1–5:

1. 1.Base case: Ift=0t=0(detected by checking ifbin​(t)\mathrm{bin}(t)is all zeros), output⟨return⟩[SEP]∥𝐯0⟨/return⟩\langle\texttt{return}\rangle\texttt{[SEP]}\mathbin{\|}\mathbf{v}_{0}\langle/\texttt{return}\ranglewhere𝐯0\mathbf{v}_{0}is the base case value (q0q_{0},0,x​[p]x[p]orbb, depending on the function).
2. 2.Recursive case: Ift>0t>0, the Transformer performs the following operations depending on the function token: - •⟨STATE⟩\langle\texttt{STATE}\rangle: (i) computet−1t-1via binary decrement; (ii) call⟨STATE⟩\langle\texttt{STATE}\rangleand⟨SYMBOL⟩\langle\texttt{SYMBOL}\ranglewith(x,t−1)(x,t-1)to obtainqt−1q_{t-1}andat−1a_{t-1}; (iii) computeδ​(qt−1,at−1)\delta(q_{t-1},a_{t-1})via lookup table to get(q′,w,d)(q^{\prime},w,d); (iv) returnq′q^{\prime}. - •⟨POS⟩\langle\texttt{POS}\rangle: (i) computet−1t-1; (ii) call⟨STATE⟩\langle\texttt{STATE}\rangleand⟨SYMBOL⟩\langle\texttt{SYMBOL}\ranglewith(x,t−1)(x,t-1); (iii) computeδ\deltato getdd; (iv) call⟨POS⟩\langle\texttt{POS}\ranglewith(x,t−1)(x,t-1)to getpt−1p_{t-1}; (v) computept−1+dp_{t-1}+dvia binary addition; (vi) returnptp_{t}. - •⟨CELL⟩\langle\texttt{CELL}\rangle: (i) computet−1t-1; (ii) call⟨POS⟩\langle\texttt{POS}\ranglewith(x,t−1)(x,t-1)to getpt−1p_{t-1}; (iii) compareppwithpt−1p_{t-1}: ifp≠pt−1p\neq p_{t-1}, recurse by calling⟨CELL⟩\langle\texttt{CELL}\ranglewith(x,t−1,p)(x,t-1,p); otherwise (iv) call⟨STATE⟩\langle\texttt{STATE}\rangleand⟨SYMBOL⟩\langle\texttt{SYMBOL}\ranglewith(x,t−1)(x,t-1), computeδ\deltato getww, and returnww. - •⟨SYMBOL⟩\langle\texttt{SYMBOL}\rangle: call⟨POS⟩\langle\texttt{POS}\ranglewith(x,t)(x,t)to getptp_{t}, then call⟨CELL⟩\langle\texttt{CELL}\ranglewith(x,t,pt)(x,t,p_{t})and return the result. - •⟨RUN⟩\langle\texttt{RUN}\rangle: (i) call⟨STATE⟩\langle\texttt{STATE}\ranglewith(x,t)(x,t)to getqtq_{t}; (ii) check ifqt∈Qacc∪Qrejq_{t}\in Q_{\mathrm{acc}}\cup Q_{\mathrm{rej}}: ifqt∈Qaccq_{t}\in Q_{\mathrm{acc}}, return11; ifqt∈Qrejq_{t}\in Q_{\mathrm{rej}}, return0; otherwise (iii) computet+1t+1via binary increment and call⟨RUN⟩\langle\texttt{RUN}\ranglewith(x,t+1)(x,t+1).
3. 3.Return processing: When a⟨/return⟩\langle/\texttt{return}\rangletoken is encountered, the stack-transition rule𝖲𝗍𝖾𝗉\mathsf{Step}pops the current frame and appends the payload[SEP]∥𝐯\texttt{[SEP]}\mathbin{\|}\mathbf{v}to the parent context, automatically incrementing the parent’s phase count.

Transformer construction.

It remains to verify that the next-token policy described above is implementable by a fixed constant-depth, constant-size Transformer with𝒪​(log⁡S​(n))\mathcal{O}(\log S(n))precision. The recursive functions𝖲𝖳𝖠𝖳𝖤\mathsf{STATE},𝖯𝖮𝖲\mathsf{POS},𝖢𝖤𝖫𝖫\mathsf{CELL},𝖲𝖸𝖬𝖡𝖮𝖫\mathsf{SYMBOL}, and𝖱𝖴𝖭\mathsf{RUN}reduce to the following primitive operations:

1. (a)Parsing the context to identify the function token⟨F⟩\langle F\rangleand extract arguments;
2. (b)Phase counting viaseq_sum: counting the number of[SEP]delimiters to determine the current computation phase;
3. (c)Binary arithmetic: increment (t↦t+1t\mapsto t+1) and decrement (t↦t−1t\mapsto t-1) of the time parameter, and position updates (p±dp\pm d), usingseq_maxfor bit-scans;
4. (d)Cache retrieval viarightmost_exact_match: retrieving previously computed values from the context;
5. (e)Finite lookups ofδ\delta,QaccQ_{\mathrm{acc}},QrejQ_{\mathrm{rej}}(hard-coded into parameters).

All primitive operations (a)–(e) above are already established in Appendix G ofYang et al. (2025a); our construction differs only in the choice of special tokens and parsing format. We refer readers to that paper for the detailed Transformer implementation. A complete construction using an alternative approach (via Alternating Turing Machines) appears in AppendixG.

Appendix GProof of Theorem1via Alternating Turing Machine

This section gives an alternative proof of Theorem1. The proof follows the classical characterization𝖳𝖨𝖬𝖤​(2O​(S​(n)))=𝖠𝖲𝖯𝖠𝖢𝖤​(O​(S​(n)))\mathsf{TIME}(2^{O(S(n))})=\mathsf{ASPACE}(O(S(n)))(Chandra–Kozen–Stockmeyer) and then realizes the resulting AND/OR computation using thecall/returnrecursion mechanism, with the per-step logic implemented by a constant-depth Transformer via Full-Access Sequence Processing (FASP)(Yang et al.,2025a).

G.1Alternating Turing Machines and𝖠𝖲𝖯𝖠𝖢𝖤\mathsf{ASPACE}

Analternating Turing machine(ATM) is a nondeterministic Turing machineA=(Γ,b,Q,q0,Δ,Qacc,Qrej)A=(\Gamma,b,Q,q_{0},\Delta,Q_{\mathrm{acc}},Q_{\mathrm{rej}})whose non-halting states are partitioned intoexistentialanduniversalstates:Q∖(Qacc∪Qrej)=Q∃​∪˙​Q∀Q\setminus(Q_{\mathrm{acc}}\cup Q_{\mathrm{rej}})=Q_{\exists}\;\dot{\cup}\;Q_{\forall}. The transition relation is a finite set

Δ⊆(Q∖(Qacc∪Qrej))×Γ×Q×Γ×{−1,0,+1}.\Delta\subseteq(Q\setminus(Q_{\mathrm{acc}}\cup Q_{\mathrm{rej}}))\times\Gamma\times Q\times\Gamma\times\{-1,0,+1\}.(32)Each tuple(q,a,q′,a′,d)∈Δ(q,a,q^{\prime},a^{\prime},d)\in\Deltaspecifies: in stateqqreading symbolaa, the machine may transition to stateq′q^{\prime}, writea′a^{\prime}on the current cell, and move the head byd∈{−1,0,+1}d\in\{-1,0,+1\}. For a configurationc=(q,τ,p)c=(q,\tau,p)(stateqq, tape contentsτ:ℤ→Γ\tau:\mathbb{Z}\to\Gamma, head positionpp), the set of successor configurations is

Succ​(c):={(q′,τ​[p↦a′],p+d):(q,τ​(p),q′,a′,d)∈Δ},\mathrm{Succ}(c):=\{(q^{\prime},\tau[p\mapsto a^{\prime}],p+d):(q,\tau(p),q^{\prime},a^{\prime},d)\in\Delta\},(33)whereτ​[p↦a′]\tau[p\mapsto a^{\prime}]denotes the tape with symbol at positionppupdated toa′a^{\prime}. Since we assume exactly two successors, we index them asSucc0​(c)\mathrm{Succ}_{0}(c)andSucc1​(c)\mathrm{Succ}_{1}(c). Fori∈{0,1}i\in\{0,1\}, letδi​(c):=(qi′,wi,di)\delta_{i}(c):=(q_{i}^{\prime},w_{i},d_{i})denote theii-th applicable transition tuple (i.e.,(q,τ​(p),qi′,wi,di)∈Δ(q,\tau(p),q_{i}^{\prime},w_{i},d_{i})\in\Delta), so thatSucci​(c)=(qi′,τ​[p↦wi],p+di)\mathrm{Succ}_{i}(c)=(q_{i}^{\prime},\tau[p\mapsto w_{i}],p+d_{i}).

Acceptance Semantics.

Fix an inputxxand letcstart​(x)c_{\mathrm{start}}(x)be the start configuration. AssumingAAis adecider(every branch halts), the acceptance value𝖶𝗂𝗇​(c)∈{0,1}\mathsf{Win}(c)\in\{0,1\}is defined recursively over the computation tree: ifcchalts inQaccQ_{\mathrm{acc}}then𝖶𝗂𝗇​(c)=1\mathsf{Win}(c)=1; if inQrejQ_{\mathrm{rej}}then𝖶𝗂𝗇​(c)=0\mathsf{Win}(c)=0; ifccis non-halting with state inQ∃Q_{\exists}, then𝖶𝗂𝗇​(c)=⋁c′∈Succ​(c)𝖶𝗂𝗇​(c′)\mathsf{Win}(c)=\bigvee_{c^{\prime}\in\mathrm{Succ}(c)}\mathsf{Win}(c^{\prime}); if inQ∀Q_{\forall}, then𝖶𝗂𝗇​(c)=⋀c′∈Succ​(c)𝖶𝗂𝗇​(c′)\mathsf{Win}(c)=\bigwedge_{c^{\prime}\in\mathrm{Succ}(c)}\mathsf{Win}(c^{\prime}). The machine acceptsxxiff𝖶𝗂𝗇​(cstart​(x))=1\mathsf{Win}(c_{\mathrm{start}}(x))=1.

Alternating Space.

The class𝖠𝖲𝖯𝖠𝖢𝖤​(S​(n))\mathsf{ASPACE}(S(n))consists of languages decidable by an ATM that visits at mostO​(S​(n))O(S(n))tape cells along every branch.

Lemma 8(Chandra–Kozen–Stockmeyer characterization).

For any space-constructibleS​(n)≥nS(n)\geq n,

𝖳𝖨𝖬𝖤​(2O​(S​(n)))=𝖠𝖲𝖯𝖠𝖢𝖤​(O​(S​(n))).\mathsf{TIME}(2^{O(S(n))})=\mathsf{ASPACE}(O(S(n))).(34)

Proof.

This is the classicalalternation theorem(Chandra et al.,1981); see also standard textbook treatments(Arora & Barak,2009). ∎

G.2Recursive Construction

Fix a space-constructibleS​(n)≥nS(n)\geq nand a languageL∈𝖳𝖨𝖬𝖤​(2O​(S​(n)))L\in\mathsf{TIME}(2^{O(S(n))}). By Lemma8, there exists an ATMAAdecidingLLin spaceO​(S​(n))O(S(n)). Decidingxxreduces to evaluating𝖶𝗂𝗇​(cstart​(x))\mathsf{Win}(c_{\mathrm{start}}(x)). SinceAAis fixed, we assume w.l.o.g. that every non-halting configuration hasexactly twosuccessors (by padding missing successors with reject for existential states and accept for universal states, and converting bounded fanout to binary). We denote the two successors bySucc0​(c)\mathrm{Succ}_{0}(c)andSucc1​(c)\mathrm{Succ}_{1}(c).

Configuration.

AconfigurationofAAis a triplec=(q,τ,p)c=(q,\tau,p)whereq∈Qq\in Qis the control state,τ:ℤ→Γ\tau:\mathbb{Z}\to\Gammais the tape contents, andp∈ℤp\in\mathbb{Z}is the head position. SinceAAusesO​(S​(n))O(S(n))space, each reachable configuration can be encoded as a token sequence𝖤𝗆𝖻𝖾𝖽​(c)\mathsf{Embed}(c)of lengthO​(S​(n))O(S(n)); the precise encoding is described in§\mathsection˜G.3.

Recursive functions.

We define the following functions for evaluating configurations:

• •𝖲𝖳𝖤𝖯​(c,i)∈{configurations}\mathsf{STEP}(c,i)\in\{\text{configurations}\}: returns theii-th successorSucci​(c)\mathrm{Succ}_{i}(c)fori∈{0,1}i\in\{0,1\}
• •𝖧𝖠𝖫𝖳𝖨𝖭𝖦​(c)∈{0,1,⊥}\mathsf{HALTING}(c)\in\{0,1,\bot\}: returns11ifc∈Qaccc\in Q_{\mathrm{acc}},0ifc∈Qrejc\in Q_{\mathrm{rej}},⊥\bototherwise
• •𝖳𝖸𝖯𝖤​(c)∈{∃,∀}\mathsf{TYPE}(c)\in\{\exists,\forall\}: returns the alternation type of non-halting configurationcc
• •𝖢𝖮𝖬𝖡​(c,b0,b1)∈{0,1}\mathsf{COMB}(c,b_{0},b_{1})\in\{0,1\}: returnsb0∨b1b_{0}\lor b_{1}if𝖳𝖸𝖯𝖤​(c)=∃\mathsf{TYPE}(c)=\exists, elseb0∧b1b_{0}\land b_{1}
• •𝖤𝖵𝖠𝖫​(c)∈{0,1}\mathsf{EVAL}(c)\in\{0,1\}: evaluates𝖶𝗂𝗇​(c)\mathsf{Win}(c)recursively

Algorithm.

The following algorithm presents the pseudocode for𝖤𝖵𝖠𝖫\mathsf{EVAL}:

Algorithm 11𝖤𝖵𝖠𝖫​(c)→b∈{0,1}\mathsf{EVAL}(c)\to b\in\{0,1\}1:if

𝖧𝖠𝖫𝖳𝖨𝖭𝖦​(c)=1\mathsf{HALTING}(c)=1then return

11⊳\trianglerightaccept

2:if

𝖧𝖠𝖫𝖳𝖨𝖭𝖦​(c)=0\mathsf{HALTING}(c)=0then return

0⊳\trianglerightreject

3:

b0←𝖤𝖵𝖠𝖫​(𝖲𝖳𝖤𝖯​(c,0))b_{0}\leftarrow\mathsf{EVAL}(\mathsf{STEP}(c,0))⊳\trianglerightevaluate first successor

4:

b1←𝖤𝖵𝖠𝖫​(𝖲𝖳𝖤𝖯​(c,1))b_{1}\leftarrow\mathsf{EVAL}(\mathsf{STEP}(c,1))⊳\trianglerightevaluate second successor

5:return

𝖢𝖮𝖬𝖡​(c,b0,b1)\mathsf{COMB}(c,b_{0},b_{1})⊳\trianglerightAND/OR combination

Correctness.

By structural induction on the computation tree:

• •*Base case:*Ifccis halting,𝖤𝖵𝖠𝖫​(c)\mathsf{EVAL}(c)returns11iffc∈Qaccc\in Q_{\mathrm{acc}}, which equals𝖶𝗂𝗇​(c)\mathsf{Win}(c)by definition.
• •*Inductive step:*Ifccis non-halting, by IH,bi=𝖤𝖵𝖠𝖫​(𝖲𝖳𝖤𝖯​(c,i))=𝖶𝗂𝗇​(Succi​(c))b_{i}=\mathsf{EVAL}(\mathsf{STEP}(c,i))=\mathsf{Win}(\mathrm{Succ}_{i}(c))fori∈{0,1}i\in\{0,1\}. Then𝖢𝖮𝖬𝖡​(c,b0,b1)\mathsf{COMB}(c,b_{0},b_{1})computes the correct AND/OR combination based on𝖳𝖸𝖯𝖤​(c)\mathsf{TYPE}(c), matching the definition of𝖶𝗂𝗇​(c)\mathsf{Win}(c).

Thus𝖤𝖵𝖠𝖫​(cstart​(x))=𝖶𝗂𝗇​(cstart​(x))\mathsf{EVAL}(c_{\mathrm{start}}(x))=\mathsf{Win}(c_{\mathrm{start}}(x)), correctly deciding whetherAAacceptsxx.

Resource analysis.

Each recursive frame stores the configuration encoding𝖤𝗆𝖻𝖾𝖽​(c)\mathsf{Embed}(c)(O​(S​(n))O(S(n))tokens), the returned bitsb0,b1b_{0},b_{1}(O​(1)O(1)bits), and call/return delimiters (O​(1)O(1)tokens), yielding local spaceO​(S​(n))O(S(n))per context. The generated call payloads𝖤𝗆𝖻𝖾𝖽​(ci)\mathsf{Embed}(c_{i})also have lengthO​(S​(n))O(S(n)), and return payloads have lengthO​(1)O(1), so the transient rollout stacks satisfy the same local-space bound. For recursion depth, an ATM usingO​(S​(n))O(S(n))space has at most2O​(S​(n))2^{O(S(n))}distinct configurations (finite control×\timeshead position×\timestape contents). BecauseAAis a decider, the configuration graph is acyclic—a cycle would induce an infinite branch. Hence the maximum recursion depth is bounded by the number of reachable configurations:2O​(S​(n))2^{O(S(n))}.

G.3Preliminaries and Setup

To implement the recursive evaluation with a Transformer, we first introduce how to represent Turing machine configurations as token sequences that the Transformer can process.

Update tokens.

We encode configurations usingupdate tokens. LetΣupd:=Q×Γ×{−1,0,+1}\Sigma_{\mathrm{upd}}:=Q\times\Gamma\times\{-1,0,+1\}be the set of update tokens, where each token(q′,w,d)(q^{\prime},w,d)represents: “writewwat the current head cell, move bydd, and set state toq′q^{\prime}”.

Update operator.

For a configurationc=(q,τ,p)c=(q,\tau,p), define theupdate operator𝖴𝗉𝖽𝖺𝗍𝖾​(c,(q′,w,d)):=(q′,τ​[p↦w],p+d)\mathsf{Update}(c,(q^{\prime},w,d)):=(q^{\prime},\tau[p\mapsto w],p+d), and extend it to sequences by𝖴𝗉𝖽𝖺𝗍𝖾​(c,x1:k):=𝖴𝗉𝖽𝖺𝗍𝖾​(𝖴𝗉𝖽𝖺𝗍𝖾​(c,x1:k−1),xk)\mathsf{Update}(c,x_{1:k}):=\mathsf{Update}(\mathsf{Update}(c,x_{1:k-1}),x_{k}). Letc𝖻𝗅𝖺𝗇𝗄:=(q0,bℤ,0)c_{\mathsf{blank}}:=(q_{0},b^{\mathbb{Z}},0)denote the blank configuration (initial state, all-blank tape, head at origin).

Translational equivalence.

Two configurationsc1=(q,τ1,p1)c_{1}=(q,\tau_{1},p_{1})andc2=(q,τ2,p2)c_{2}=(q,\tau_{2},p_{2})aretranslationally equivalent, writtenc1∼c2c_{1}\sim c_{2}, if there existsk∈ℤk\in\mathbb{Z}such thatτ1​(i)=τ2​(i−k)\tau_{1}(i)=\tau_{2}(i-k)for alliiandp1=p2+kp_{1}=p_{2}+k. Intuitively, they differ only by a shift in absolute tape coordinates. This relation preserves halting status and successor structure.

Configuration embedding.

The embedding𝖤𝗆𝖻𝖾𝖽:(Q×Γℤ×ℤ)→Σupd∗\mathsf{Embed}:(Q\times\Gamma^{\mathbb{Z}}\times\mathbb{Z})\to\Sigma_{\mathrm{upd}}^{*}maps a configurationc=(q,τ,p)c=(q,\tau,p)to the canonical token sequence that “walks through” the non-blank tape region. Formally, for a tapeτ\tau, defineℓ​(τ):=min⁡({0}∪{i:τ​(i)≠b})\ell(\tau):=\min(\{0\}\cup\{i:\tau(i)\neq b\})andr​(τ):=max⁡({0}∪{i:τ​(i)≠b})r(\tau):=\max(\{0\}\cup\{i:\tau(i)\neq b\})as the left and right boundaries of the non-blank region. Then𝖤𝗆𝖻𝖾𝖽​(c)\mathsf{Embed}(c)is a sequence of tokens(q,ai,di)(q,a_{i},d_{i})where eachaia_{i}is the tape symbol at positionℓ​(τ)+∑j<idj\ell(\tau)+\sum_{j<i}d_{j}and the movesdi∈{−1,0,+1}d_{i}\in\{-1,0,+1\}are chosen so that the sequence “walks through” the interval[ℓ​(τ),r​(τ)][\ell(\tau),r(\tau)]and ends with the head aligned topp. By construction,𝖴𝗉𝖽𝖺𝗍𝖾​(c𝖻𝗅𝖺𝗇𝗄,𝖤𝗆𝖻𝖾𝖽​(c))∼c\mathsf{Update}(c_{\mathsf{blank}},\mathsf{Embed}(c))\sim c. (Note: while many token sequences can produce the same configuration,𝖤𝗆𝖻𝖾𝖽\mathsf{Embed}is adeterministicfunction that outputs a canonical representation.)

Since the ATM usesO​(S​(n))O(S(n))space,|𝖤𝗆𝖻𝖾𝖽​(c)|=O​(S​(n))|\mathsf{Embed}(c)|=O(S(n))for all reachable configurations. Each transition tupleδi​(c)=(qi′,wi,di)∈Σupd\delta_{i}(c)=(q_{i}^{\prime},w_{i},d_{i})\in\Sigma_{\mathrm{upd}}is a single update token. Appendingδi​(c)\delta_{i}(c)to𝖤𝗆𝖻𝖾𝖽​(c)\mathsf{Embed}(c)yields an update sequence that represents the successor up to translation:𝖴𝗉𝖽𝖺𝗍𝖾​(c𝖻𝗅𝖺𝗇𝗄,𝖤𝗆𝖻𝖾𝖽​(c)∥δi​(c))∼Succi​(c)\mathsf{Update}(c_{\mathsf{blank}},\,\mathsf{Embed}(c)\mathbin{\|}\delta_{i}(c))\sim\mathrm{Succ}_{i}(c). Define the canonicalization operator𝖢𝖺𝗇𝗈𝗇:Σupd∗→Σupd∗\mathsf{Canon}:\Sigma_{\mathrm{upd}}^{*}\to\Sigma_{\mathrm{upd}}^{*}by𝖢𝖺𝗇𝗈𝗇​(z):=𝖤𝗆𝖻𝖾𝖽​(𝖴𝗉𝖽𝖺𝗍𝖾​(c𝖻𝗅𝖺𝗇𝗄,z))\mathsf{Canon}(z):=\mathsf{Embed}(\mathsf{Update}(c_{\mathsf{blank}},z)). Then𝖢𝖺𝗇𝗈𝗇​(𝖤𝗆𝖻𝖾𝖽​(c))=𝖤𝗆𝖻𝖾𝖽​(c)\mathsf{Canon}(\mathsf{Embed}(c))=\mathsf{Embed}(c)and

𝖤𝗆𝖻𝖾𝖽​(Succi​(c))=𝖢𝖺𝗇𝗈𝗇​(𝖤𝗆𝖻𝖾𝖽​(c)∥δi​(c)).\mathsf{Embed}(\mathrm{Succ}_{i}(c))=\mathsf{Canon}(\mathsf{Embed}(c)\mathbin{\|}\delta_{i}(c)).(35)

G.4Transformer Construction

We now describe how the Transformer autoregressively generates tokens to implement the recursive evaluation.

Call/return mechanism.

As in the primary proof, we use control tokens⟨call⟩,⟨/call⟩,⟨return⟩,⟨/return⟩\langle\texttt{call}\rangle,\langle/\texttt{call}\rangle,\langle\texttt{return}\rangle,\langle/\texttt{return}\rangleto implement recursion:

𝖢𝖠𝖫𝖫(c):=⟨call⟩𝖤𝗆𝖻𝖾𝖽(c)⟨/call⟩,𝖱𝖤𝖳(b):=⟨return⟩b⟨/return⟩.\mathsf{CALL}(c):=\langle\texttt{call}\rangle\mathsf{Embed}(c)\langle/\texttt{call}\rangle,\qquad\mathsf{RET}(b):=\langle\texttt{return}\rangle b\langle/\texttt{return}\rangle.(36)Completing𝖢𝖠𝖫𝖫​(c)\mathsf{CALL}(c)pushes𝖤𝗆𝖻𝖾𝖽​(c)\mathsf{Embed}(c)as a child context and removes the call block from the parent; completing𝖱𝖤𝖳​(b)\mathsf{RET}(b)pops and appendsbbto the parent.

Evaluation transcript.

For a configurationc=(q,τ,p)c=(q,\tau,p), we describe the step-by-step token generation. Recall that for non-haltingcc, there are exactly two applicable transitions yielding successorsci:=𝖲𝖳𝖤𝖯​(c,i)c_{i}:=\mathsf{STEP}(c,i)withbi:=𝖶𝗂𝗇​(ci)b_{i}:=\mathsf{Win}(c_{i}).

For non-haltingcc, the active context cycles through three phases:

𝖤𝗆𝖻𝖾𝖽​(c)→step 1𝖤𝗆𝖻𝖾𝖽​(c)∥b0→step 2𝖤𝗆𝖻𝖾𝖽​(c)∥b0∥b1→step 3return.\mathsf{Embed}(c)\quad\xrightarrow{\text{step 1}}\quad\mathsf{Embed}(c)\mathbin{\|}b_{0}\quad\xrightarrow{\text{step 2}}\quad\mathsf{Embed}(c)\mathbin{\|}b_{0}\mathbin{\|}b_{1}\quad\xrightarrow{\text{step 3}}\quad\text{return}.(37)In step 1, the generator emits𝖢𝖠𝖫𝖫​(c0)\mathsf{CALL}(c_{0}), where the call payload is the canonical embedding𝖤𝗆𝖻𝖾𝖽​(c0)=𝖢𝖺𝗇𝗈𝗇​(𝖤𝗆𝖻𝖾𝖽​(c)∥δ0​(c))\mathsf{Embed}(c_{0})=\mathsf{Canon}(\mathsf{Embed}(c)\mathbin{\|}\delta_{0}(c)); the child returnsb0b_{0}. In step 2, similarly forc1c_{1}. In step 3, it emits𝖱𝖤𝖳​(𝖢𝖮𝖬𝖡​(c,b0,b1))\mathsf{RET}(\mathsf{COMB}(c,b_{0},b_{1})). We now describe each step in detail.

*Halting case:*Ifccis halting, the context is𝖤𝗆𝖻𝖾𝖽​(c)\mathsf{Embed}(c)and the generator emits𝖱𝖤𝖳​(𝖶𝗂𝗇​(c))\mathsf{RET}(\mathsf{Win}(c)).

*Non-halting case:*Ifccis non-halting, letci:=𝖴𝗉𝖽𝖺𝗍𝖾​(c,δi​(c))=Succi​(c)c_{i}:=\mathsf{Update}(c,\delta_{i}(c))=\mathrm{Succ}_{i}(c)fori∈{0,1}i\in\{0,1\}:

1. 1.Context:𝖤𝗆𝖻𝖾𝖽​(c)\mathsf{Embed}(c)→\toGenerate:𝖢𝖠𝖫𝖫​(c0)\mathsf{CALL}(c_{0}); child recurses and returnsb0b_{0}. The generator first computes the update tokenδ0​(c)∈Σupd\delta_{0}(c)\in\Sigma_{\mathrm{upd}}and then emits𝖢𝖠𝖫𝖫​(c0)\mathsf{CALL}(c_{0})whose payload is the canonical embedding𝖤𝗆𝖻𝖾𝖽​(c0)=𝖢𝖺𝗇𝗈𝗇​(𝖤𝗆𝖻𝖾𝖽​(c)∥δ0​(c))\mathsf{Embed}(c_{0})=\mathsf{Canon}(\mathsf{Embed}(c)\mathbin{\|}\delta_{0}(c)). The child recursively evaluatesc0c_{0}and returnsb0=𝖶𝗂𝗇​(c0)b_{0}=\mathsf{Win}(c_{0}). After return, the parent context becomes𝖤𝗆𝖻𝖾𝖽​(c)∥b0\mathsf{Embed}(c)\mathbin{\|}b_{0}.
2. 2.Context:𝖤𝗆𝖻𝖾𝖽​(c)∥b0\mathsf{Embed}(c)\mathbin{\|}b_{0}→\toGenerate:𝖢𝖠𝖫𝖫​(c1)\mathsf{CALL}(c_{1}); child recurses and returnsb1b_{1}. Similarly, the generator emits𝖢𝖠𝖫𝖫​(c1)\mathsf{CALL}(c_{1})with payload𝖤𝗆𝖻𝖾𝖽​(c1)=𝖢𝖺𝗇𝗈𝗇​(𝖤𝗆𝖻𝖾𝖽​(c)∥δ1​(c))\mathsf{Embed}(c_{1})=\mathsf{Canon}(\mathsf{Embed}(c)\mathbin{\|}\delta_{1}(c)). The child returnsb1=𝖶𝗂𝗇​(c1)b_{1}=\mathsf{Win}(c_{1}). After return, the parent context becomes𝖤𝗆𝖻𝖾𝖽​(c)∥b0∥b1\mathsf{Embed}(c)\mathbin{\|}b_{0}\mathbin{\|}b_{1}.
3. 3.Context:𝖤𝗆𝖻𝖾𝖽​(c)∥b0∥b1\mathsf{Embed}(c)\mathbin{\|}b_{0}\mathbin{\|}b_{1}→\toGenerate:𝖱𝖤𝖳​(𝖢𝖮𝖬𝖡​(c,b0,b1))\mathsf{RET}(\mathsf{COMB}(c,b_{0},b_{1})). With both resultsb0,b1b_{0},b_{1}available, the generator computes𝖢𝖮𝖬𝖡​(c,b0,b1)\mathsf{COMB}(c,b_{0},b_{1})(AND ifc∈Q∀c\in Q_{\forall}, OR ifc∈Q∃c\in Q_{\exists}) and emits the return block, completing the evaluation ofcc.

Transformer construction.

It remains to verify that the next-token policy is implementable by a fixed constant-depth, constant-size Transformer with𝒪​(log⁡S​(n))\mathcal{O}(\log S(n))precision. The recursive evaluation of𝖤𝖵𝖠𝖫​(c)\mathsf{EVAL}(c)reduces to the following primitive operations:

1. (a)Parsing the configuration embedding prefix𝖤𝗆𝖻𝖾𝖽​(c)\mathsf{Embed}(c)to extract the current stateqq(reading the state component of any update token in𝖤𝗆𝖻𝖾𝖽​(c)\mathsf{Embed}(c));
2. (b)Halting and alternation-type detection: checkingq∈Qacc∪Qrejq\in Q_{\mathrm{acc}}\cup Q_{\mathrm{rej}}andq∈Q∃q\in Q_{\exists}vs.q∈Q∀q\in Q_{\forall}(constant-size set membership);
3. (c)Computing the head positionppas a prefix sum of moves in𝖤𝗆𝖻𝖾𝖽​(c)\mathsf{Embed}(c)(viaseq_sum);
4. (d)Retrieving the scanned symbola=τ​(p)a=\tau(p)via a “rightmost match” query: find the most recent update token in𝖤𝗆𝖻𝖾𝖽​(c)\mathsf{Embed}(c)that wrote to positionpp(viarightmost_exact_match);
5. (e)Computing the successor transitionδi​(c)=(qi′,wi,di)\delta_{i}(c)=(q_{i}^{\prime},w_{i},d_{i})via finite lookup on(q,a)(q,a)(hard-coded into parameters);
6. (f)Computing𝖢𝖮𝖬𝖡​(c,b0,b1)\mathsf{COMB}(c,b_{0},b_{1}): AND/OR of returned bits based on alternation type (local gates);
7. (g)Canonicalization: generating the call payload𝖤𝗆𝖻𝖾𝖽​(ci)=𝖢𝖺𝗇𝗈𝗇​(𝖤𝗆𝖻𝖾𝖽​(c)∥δi​(c))\mathsf{Embed}(c_{i})=\mathsf{Canon}(\mathsf{Embed}(c)\mathbin{\|}\delta_{i}(c))fori∈{0,1}i\in\{0,1\}. This re-embeds the successor configuration by walking through the updated tape using (c) and (d) with the new stateqi′q_{i}^{\prime}, new head positionp+dip+d_{i}, and tape symbolwiw_{i}at positionpp. The output length is|𝖤𝗆𝖻𝖾𝖽​(ci)|=O​(S​(n))|\mathsf{Embed}(c_{i})|=O(S(n)).

All primitive operations (a)–(g) above are already established in Appendix G ofYang et al. (2025a); our construction differs only in the choice of special tokens and parsing format. We refer readers to that paper for the detailed Transformer implementation.

Conclusion.

By FASP-to-Transformer compilation(Yang et al.,2025a), the next-token rule can be implemented by a fixed constant-depth Transformerfθf_{\theta}withO​(log⁡S​(n))O(\log S(n))precision. The recursive model with generatorfθf_{\theta}decidesLLwith local spaceO​(S​(n))O(S(n))and recursion depth2O​(S​(n))2^{O(S(n))}. ThereforeL∈𝖱𝖬​(O​(S​(n)),2O​(S​(n)))L\in\mathsf{RM}(O(S(n)),2^{O(S(n))}), completing the alternative proof of Theorem1.

Appendix HProof of Theorem2

Proof.

Both inclusions are a direct corollary of the chain-of-thought characterization inMerrill & Sabharwal (2024). WhenD=1D=1(no recursive calls), the recursive model reduces to standard autoregressive generation: the sequence grows monotonically until the model emits a return token, so the local space bound𝒪​(S​(n))\mathcal{O}(S(n))directly limits the total number of generated tokens to𝒪​(S​(n))\mathcal{O}(S(n)). Settingt​(n)=Θ​(S​(n))t(n)=\Theta(S(n))in their Eq. (1) and usingS​(n)≥nS(n)\geq nyields𝖳𝖨𝖬𝖤​(𝒪​(S​(n)))⊆𝖱𝖬​(𝒪​(S​(n)),1)\mathsf{TIME}(\mathcal{O}(S(n)))\subseteq\mathsf{RM}(\mathcal{O}(S(n)),1)and𝖱𝖬​(𝒪​(S​(n)),1)⊆𝖳𝖨𝖬𝖤​(𝒪~​(S2​(n)))\mathsf{RM}(\mathcal{O}(S(n)),1)\subseteq\mathsf{TIME}(\widetilde{\mathcal{O}}(S^{2}(n))), where the𝒪~​(⋅)\widetilde{\mathcal{O}}(\cdot)absorbs the polylogarithmic overhead from simulating𝒪​(log⁡S​(n))\mathcal{O}(\log S(n))-precision arithmetic on a Turing machine. ∎

Appendix IProof of Theorem3

Theorem 9(Constant-Depth Recursive Models, Formal).

For anyS​(n)≥nS(n)\geq n, recursive models with constant recursion depthD=O​(1)D=O(1)and local space𝒪​(S​(n))\mathcal{O}(S(n))can solve any problem in𝖲𝖯𝖠𝖢𝖤​(S​(n))\mathsf{SPACE}(S(n)):

𝖲𝖯𝖠𝖢𝖤​(S​(n))⊆𝖱𝖬​(𝒪​(S​(n)),𝒪​(1)).\mathsf{SPACE}(S(n))\subseteq\mathsf{RM}(\mathcal{O}(S(n)),\mathcal{O}(1)).(38)Moreover, for anyT:ℕ→ℕT:\mathbb{N}\to\mathbb{N},

𝖳𝖬​(S​(n),T​(n))⊆𝖱𝖬​(𝒪​(S​(n)),𝒪​(1),𝒪​(T​(n))).\mathsf{TM}(S(n),T(n))\subseteq\mathsf{RM}(\mathcal{O}(S(n)),\mathcal{O}(1),\mathcal{O}(T(n))).(39)

Proof.

Fix any languageL∈𝖲𝖯𝖠𝖢𝖤​(𝒪​(S​(n)))L\in\mathsf{SPACE}(\mathcal{O}(S(n)))and let𝖳𝖬=(Γ,b,Q,q0,δ,Qacc,Qrej)\mathsf{TM}=(\Gamma,b,Q,q_{0},\delta,Q_{\mathrm{acc}},Q_{\mathrm{rej}})be a deterministic single-tape Turing machine decidingLLusing at mostc⋅S​(n)c\cdot S(n)tape cells on inputs of lengthnn. We construct a constant-size Transformerfθ​(L)f_{\theta(L)}such that the recursive model withfθ​(L)f_{\theta(L)}simulates𝖳𝖬\mathsf{TM}with recursion depthD=2D=2and local space𝒪​(S​(n))\mathcal{O}(S(n))in a time- and space-efficient manner. If this same machine also halts withinT​(n)T(n)steps, the token-efficiency analysis below gives the strengthened membership in𝖱𝖬​(𝒪​(S​(n)),𝒪​(1),𝒪​(T​(n)))\mathsf{RM}(\mathcal{O}(S(n)),\mathcal{O}(1),\mathcal{O}(T(n))).

Configuration.

Aconfigurationof𝖳𝖬\mathsf{TM}is a triplec=(q,τ,p)c=(q,\tau,p)where:

• •q∈Qq\in Qis the current control state;
• •τ:ℤ→Γ\tau:\mathbb{Z}\to\Gammais thetape contents, a function mapping each cell index to a symbol, withτ​(i)=b\tau(i)=b(the blank symbol) for all but finitely manyii;
• •p∈ℤp\in\mathbb{Z}is the head position.

For a tapeτ\tauand positionpp, we writeτ​[p↦w]\tau[p\mapsto w]for the tape that agrees withτ\taueverywhere except at positionpp, where it holds symbolww.

Update tokens and the update operator.

LetΣupd:=Q×Γ×{−1,0,+1}\Sigma_{\mathrm{upd}}:=Q\times\Gamma\times\{-1,0,+1\}. We interpret a tokenx=(q′,w,d)∈Σupdx=(q^{\prime},w,d)\in\Sigma_{\mathrm{upd}}as anupdate: “writewwat the current head cell, move bydd, and set the control state toq′q^{\prime}”. For a configurationc=(q,τ,p)c=(q,\tau,p), define

𝖴𝗉𝖽𝖺𝗍𝖾​(c,(q′,w,d)):=(q′,τ​[p↦w],p+d),\mathsf{Update}(c,(q^{\prime},w,d)):=(q^{\prime},\tau[p\mapsto w],p+d),(40)and extend𝖴𝗉𝖽𝖺𝗍𝖾\mathsf{Update}to sequencesx1:k∈Σupd∗x_{1:k}\in\Sigma_{\mathrm{upd}}^{*}by𝖴𝗉𝖽𝖺𝗍𝖾​(c,x1:k):=𝖴𝗉𝖽𝖺𝗍𝖾​(𝖴𝗉𝖽𝖺𝗍𝖾​(c,x1:k−1),xk)\mathsf{Update}(c,x_{1:k}):=\mathsf{Update}(\mathsf{Update}(c,x_{1:k-1}),x_{k}). We also extendδ\deltato configurations byδ​(q,τ,p):=δ​(q,τ​(p))\delta(q,\tau,p):=\delta(q,\tau(p)).

Translational equivalence.

Two configurationsc1=(q,τ1,p1)c_{1}=(q,\tau_{1},p_{1})andc2=(q,τ2,p2)c_{2}=(q,\tau_{2},p_{2})aretranslationally equivalent, writtenc1∼c2c_{1}\sim c_{2}, if there existsk∈ℤk\in\mathbb{Z}such thatτ1​(i)=τ2​(i−k)\tau_{1}(i)=\tau_{2}(i-k)for alli∈ℤi\in\mathbb{Z}andp1=p2+kp_{1}=p_{2}+k. Intuitively, two configurations are translationally equivalent if they differ only by a shift in absolute tape coordinates, while their control state, tape contents, and the head’s relative position within the tape are identical. This relation preserves the next update and halting status:c1∼c2⇒δ​(c1)=δ​(c2)c_{1}\sim c_{2}\Rightarrow\delta(c_{1})=\delta(c_{2}).

Configuration embedding.

For a tapeτ\tau, defineℓ​(τ):=min⁡({0}∪{i:τ​(i)≠b})\ell(\tau):=\min(\{0\}\cup\{i:\tau(i)\neq b\})andr​(τ):=max⁡({0}∪{i:τ​(i)≠b})r(\tau):=\max(\{0\}\cup\{i:\tau(i)\neq b\}). The embedding𝖤𝗆𝖻𝖾𝖽:(Q×Γℤ×ℤ)→Σupd∗\mathsf{Embed}:(Q\times\Gamma^{\mathbb{Z}}\times\mathbb{Z})\to\Sigma_{\mathrm{upd}}^{*}maps a configurationc=(q,τ,p)c=(q,\tau,p)to a sequence(x1,…,xm)(x_{1},\ldots,x_{m})where eachxi=(q,ai,di)x_{i}=(q,a_{i},d_{i}), withaia_{i}being the tape symbol at positionℓ​(τ)+∑j<idj\ell(\tau)+\sum_{j<i}d_{j}anddi∈{−1,0,+1}d_{i}\in\{-1,0,+1\}chosen so that the sequence “walks through” the non-blank interval[ℓ​(τ),r​(τ)][\ell(\tau),r(\tau)]and ends with the head aligned topp. Letc𝖻𝗅𝖺𝗇𝗄:=(q0,bℤ,0)c_{\mathsf{blank}}:=(q_{0},b^{\mathbb{Z}},0)be the blank configuration. Then𝖴𝗉𝖽𝖺𝗍𝖾​(c𝖻𝗅𝖺𝗇𝗄,𝖤𝗆𝖻𝖾𝖽​(c))∼c\mathsf{Update}(c_{\mathsf{blank}},\mathsf{Embed}(c))\sim c. (Note: while many token sequences can produce the same configuration,𝖤𝗆𝖻𝖾𝖽\mathsf{Embed}is adeterministicfunction that outputs a canonical representation; the proof only requires𝖴𝗉𝖽𝖺𝗍𝖾​(c𝖻𝗅𝖺𝗇𝗄,𝖤𝗆𝖻𝖾𝖽​(c))∼c\mathsf{Update}(c_{\mathsf{blank}},\mathsf{Embed}(c))\sim c.)

Since𝖳𝖬\mathsf{TM}is space-bounded,|𝖤𝗆𝖻𝖾𝖽​(c)|=𝒪​(S​(n))|\mathsf{Embed}(c)|=\mathcal{O}(S(n))for all reachable configurations. LetN:=C⋅S​(n)N:=C\cdot S(n)for a sufficiently large constantCCsuch that|𝖤𝗆𝖻𝖾𝖽​(c)|≤N|\mathsf{Embed}(c)|\leq Nfor every reachable configuration.

Depth-1 frame.

The depth-1 frame is the outermost frame and serves as a “dispatcher”. Its role is simple: whenever its suffix matches⟨call⟩​w\langle\texttt{call}\rangle\,wfor some stringww, it emits the closing token⟨/call⟩\langle/\texttt{call}\rangle, which triggers a push of a new depth-2 frame with contentww. This mechanism enables tail-call elimination: when the depth-2 frame returns an open call-prefix, the depth-1 frame completes the call and activates a fresh depth-2 frame.

Depth-2 frame.

The depth-2 frame is the active simulation frame. It stores

𝖥𝗋𝖺𝗆𝖾​(z,u):=z∥⟨sep⟩∥u,\mathsf{Frame}(z,u):=z\mathbin{\|}\langle\texttt{sep}\rangle\mathbin{\|}u,(41)wherez∈Σupd∗z\in\Sigma_{\mathrm{upd}}^{*}is thesummarized history(the embedding of all past computation) andu∈Σupd∗u\in\Sigma_{\mathrm{upd}}^{*}is thenew trace(updates generated since the last summarization). The current simulated configuration is recovered by

c∗:=𝖢𝗈𝗇𝖿​(z,u):=𝖴𝗉𝖽𝖺𝗍𝖾​(c𝖻𝗅𝖺𝗇𝗄,z∥u),c^{*}:=\mathsf{Conf}(z,u):=\mathsf{Update}(c_{\mathsf{blank}},z\mathbin{\|}u),(42)where the delimiter⟨sep⟩\langle\texttt{sep}\rangleis ignored by𝖴𝗉𝖽𝖺𝗍𝖾\mathsf{Update}.

Next-token policy (simulation vs. summarization).

Given𝖥𝗋𝖺𝗆𝖾​(z,u)\mathsf{Frame}(z,u), letc∗=(q∗,τ∗,p∗)=𝖢𝗈𝗇𝖿​(z,u)c^{*}=(q^{*},\tau^{*},p^{*})=\mathsf{Conf}(z,u). The next-token policy operates as follows:

1. (i)Halting:Ifq∗∈Qaccq^{*}\in Q_{\mathrm{acc}}(resp.QrejQ_{\mathrm{rej}}), emit⟨return⟩1⟨/return⟩\langle\texttt{return}\rangle 1\langle/\texttt{return}\rangle(resp.⟨return⟩0⟨/return⟩\langle\texttt{return}\rangle 0\langle/\texttt{return}\rangle) and halt.
2. (ii)Simulation mode:Ifq∗∉Qacc∪Qrejq^{*}\notin Q_{\mathrm{acc}}\cup Q_{\mathrm{rej}}and|u|<2​N|u|<2N, emit the single update tokenδ​(c∗)∈Σupd\delta(c^{*})\in\Sigma_{\mathrm{upd}}. This appends exactly one TM step to the new traceuu.
3. (iii)Summarization mode:If|u|=2​N|u|=2N, compute the summarized statez′:=𝖤𝗆𝖻𝖾𝖽​(c∗)z^{\prime}:=\mathsf{Embed}(c^{*})and emit⟨return⟩⟨call⟩𝖥𝗋𝖺𝗆𝖾(z′,ϵ)⟨/return⟩\langle\texttt{return}\rangle\langle\texttt{call}\rangle\,\mathsf{Frame}(z^{\prime},\epsilon)\langle/\texttt{return}\rangle. Under the recursive-model stack semantics, this returns an open call-prefix to the depth-1 frame, which then emits⟨/call⟩\langle/\texttt{call}\rangleand activates a new depth-2 frame𝖥𝗋𝖺𝗆𝖾​(z′,ϵ)\mathsf{Frame}(z^{\prime},\epsilon).

Correctness and resource analysis.

We now verify that the construction is correct and analyze its resource consumption: local space𝒪​(S​(n))\mathcal{O}(S(n)), recursion depth22, and token efficiency𝒪​(T)\mathcal{O}(T)whereTTis the number of TM steps.

Correctness.

We maintain the invariant that at all times the depth-2 frame represents the current TM configuration (up to translation): afterttsimulated steps since the last summarization,𝖢𝗈𝗇𝖿​(z,u)∼ct\mathsf{Conf}(z,u)\sim c_{t}, wherectc_{t}is the true𝖳𝖬\mathsf{TM}configuration afterttsteps. The base case follows from𝖴𝗉𝖽𝖺𝗍𝖾​(c𝖻𝗅𝖺𝗇𝗄,𝖤𝗆𝖻𝖾𝖽​(c0))∼c0\mathsf{Update}(c_{\mathsf{blank}},\mathsf{Embed}(c_{0}))\sim c_{0}. In simulation mode, emittingδ​(𝖢𝗈𝗇𝖿​(z,u))\delta(\mathsf{Conf}(z,u))advances the configuration by one𝖴𝗉𝖽𝖺𝗍𝖾\mathsf{Update}, matching one TM transition sinceδ\deltais invariant under∼\sim. In summarization mode, replacing(z,u)(z,u)by(𝖤𝗆𝖻𝖾𝖽​(𝖢𝗈𝗇𝖿​(z,u)),ϵ)(\mathsf{Embed}(\mathsf{Conf}(z,u)),\epsilon)preserves the represented configuration since𝖴𝗉𝖽𝖺𝗍𝖾​(c𝖻𝗅𝖺𝗇𝗄,𝖤𝗆𝖻𝖾𝖽​(𝖢𝗈𝗇𝖿​(z,u)))∼𝖢𝗈𝗇𝖿​(z,u)\mathsf{Update}(c_{\mathsf{blank}},\mathsf{Embed}(\mathsf{Conf}(z,u)))\sim\mathsf{Conf}(z,u). Thus the model returns the correct accept/reject decision.

Local space.

During simulation, the depth-2 frame has length|z|+1+|u|≤N+1+2​N=3​N+1=𝒪​(S​(n))|z|+1+|u|\leq N+1+2N=3N+1=\mathcal{O}(S(n)). During summarization, the return payload contributes at most|z′|+𝒪​(1)=𝒪​(S​(n))|z^{\prime}|+\mathcal{O}(1)=\mathcal{O}(S(n))additional tokens, so local space remains𝒪​(S​(n))\mathcal{O}(S(n)). Thus the bound applies both to stored frames and to transient rollout outputs. The stack height is always at most22.

Token efficiency.

Each TM step produces exactly one emitted update token in simulation mode. A summarization happens once every2​N2Nsimulated steps and emits at most|z′|+𝒪​(1)≤N+𝒪​(1)|z^{\prime}|+\mathcal{O}(1)\leq N+\mathcal{O}(1)tokens. If𝖳𝖬\mathsf{TM}halts afterTTsteps, the total number of emitted tokens is

T+𝒪​(T2​N)⋅(N+𝒪​(1))=𝒪​(T),T+\mathcal{O}\!\left(\frac{T}{2N}\right)\cdot(N+\mathcal{O}(1))=\mathcal{O}(T),(43)which is linear inTT.

Transformer construction.

It remains to verify that the next-token policy is implementable by a fixed constant-depth, constant-size Transformer with𝒪​(log⁡n)\mathcal{O}(\log n)precision. Bothδ​(⋅)\delta(\cdot)and𝖤𝗆𝖻𝖾𝖽​(⋅)\mathsf{Embed}(\cdot)reduce to the following primitive operations:

1. (a)Parsing the summarized historyzzand new traceuu(fixed-format tokenized strings);
2. (b)Computing the head position as a prefix sum of moves inz∥uz\mathbin{\|}u(arithmetic on𝒪​(log⁡S​(n))\mathcal{O}(\log S(n))-bit integers);
3. (c)Retrieving the current tape symbol via a “rightmost match” query: for a given head position, find the most recent update token inz∥uz\mathbin{\|}uthat wrote to that cell;
4. (d)A finite lookup ofδ\delta(hard-coded into parameters).

All primitive operations (a)–(d) above are already established in Appendix G ofYang et al. (2025a); our construction differs only in the choice of special tokens and parsing format. We refer readers to that paper for the detailed Transformer implementation.

IfL∈𝖳𝖬​(S​(n),T​(n))L\in\mathsf{TM}(S(n),T(n)), choose the witnessing Turing machine that simultaneously uses𝒪​(S​(n))\mathcal{O}(S(n))space and𝒪​(T​(n))\mathcal{O}(T(n))time. The construction above then gives recursion depth22, local space𝒪​(S​(n))\mathcal{O}(S(n)), and𝒪​(T​(n))\mathcal{O}(T(n))generated tokens, soL∈𝖱𝖬​(𝒪​(S​(n)),𝒪​(1),𝒪​(T​(n)))L\in\mathsf{RM}(\mathcal{O}(S(n)),\mathcal{O}(1),\mathcal{O}(T(n))). Dropping the time bound yields, for arbitraryL∈𝖲𝖯𝖠𝖢𝖤​(𝒪​(S​(n)))L\in\mathsf{SPACE}(\mathcal{O}(S(n))), the inclusionL∈𝖱𝖬​(𝒪​(S​(n)),2)L\in\mathsf{RM}(\mathcal{O}(S(n)),2). ∎

Appendix JPreliminaries for Section4

J.1Strings

Fix a finite token alphabetΣ\Sigma. We writeΣ∗\Sigma^{*}for the set of all finite token strings and|x||x|for the length ofx∈Σ∗x\in\Sigma^{*}. For a length boundLL, defineΣ≤L:={z∈Σ∗:|z|≤L}\Sigma_{\leq L}:=\{z\in\Sigma^{*}:|z|\leq L\}. Note that|Σ≤L|≤∑i=0L|Σ|i=2O​(L)|\Sigma_{\leq L}|\leq\sum_{i=0}^{L}|\Sigma|^{i}=2^{O(L)}.

J.2Polynomial-Time Generators

A generatorffispolynomial-timeif there exists a deterministic Turing machine that computesf​(x)f(x)fromxxin timepoly​(|x|+|f​(x)|)\mathrm{poly}(|x|+|f(x)|). A generator familyℱ=(f1,…,fk)\mathcal{F}=(f_{1},\ldots,f_{k})is polynomial-time if eachfℓf_{\ell}is polynomial-time.

J.3Oracle Turing Machine

Adeterministic oracle Turing machine(OTM) is a deterministic multi-tape Turing machine equipped with, for each oracle nameooin a finite index set𝒩\mathcal{N}, anoracle query tapeand anoracle answer tape. Each oracle is a total function𝒪o:Σ∗→Σ∗\mathcal{O}_{o}:\Sigma^{*}\to\Sigma^{*}.

Query/Answer Mechanism.

When the machine enters a distinguishedquery stateqask,oq_{\mathrm{ask},o}, the string currently written on the oracle-ooquery tape (from cell0to the first blank) is taken as the queryuu. In one transition, the oracle answer tape is overwritten with𝒪o​(u)\mathcal{O}_{o}(u)(starting at cell0), and the machine enters a distinguishedreturn stateqret,oq_{\mathrm{ret},o}.

Resource Measures.

Time counts ordinary TM transitions (including transitions into and out of query/return states). Space counts the number of distinct tape cells visited onwork tapes(excluding the read-only input tape and oracle tapes).

Relativized Complexity Classes.

For a fixed oracle familyΩ=(𝒪1,…,𝒪k)\Omega=(\mathcal{O}_{1},\ldots,\mathcal{O}_{k}):

𝖣𝖳𝖨𝖬𝖤Ω​(f​(n))\displaystyle\mathsf{DTIME}^{\Omega}(f(n))={L:∃OTM with access to​Ω​deciding​L​in​O​(f​(n))​time},\displaystyle=\{L:\exists\,\text{OTM with access to }\Omega\text{ deciding }L\text{ in }O(f(n))\text{ time}\},(44)𝖣𝖲𝖯𝖠𝖢𝖤Ω​(f​(n))\displaystyle\mathsf{DSPACE}^{\Omega}(f(n))={L:∃OTM with access to​Ω​deciding​L​in​O​(f​(n))​work space}.\displaystyle=\{L:\exists\,\text{OTM with access to }\Omega\text{ deciding }L\text{ in }O(f(n))\text{ work space}\}.(45)

Recursive-Call Variant.

In the main text, a scaffold is formalized as an OTM-style procedure whose query names are

𝖦𝖤𝖭1,…,𝖦𝖤𝖭kand𝖲𝖤𝖫𝖥1,…,𝖲𝖤𝖫𝖥m.\mathsf{GEN}_{1},\ldots,\mathsf{GEN}_{k}\qquad\text{and}\qquad\mathsf{SELF}_{1},\ldots,\mathsf{SELF}_{m}.The names𝖦𝖤𝖭ℓ\mathsf{GEN}_{\ell}are interpreted by the given generator functionsfℓf_{\ell}. The names𝖲𝖤𝖫𝖥j\mathsf{SELF}_{j}are recursive-call interfaces; their meanings are not fixed in advance, but are solved by the least-fixpoint construction in§\mathsection˜J.4.

Alternating Turing Machines.

Analternating Turing machine(ATM) extends a nondeterministic TM by labeling each state as eitherexistential(∃\exists) oruniversal(∀\forall). At an∃\exists-state, the machine accepts ifsomesuccessor configuration accepts; at a∀\forall-state, it accepts ifallsuccessor configurations accept. We write𝖠𝖲𝖯𝖠𝖢𝖤​(S​(n))\mathsf{ASPACE}(S(n))for the class of languages decidable by an ATM using spaceO​(S​(n))O(S(n)).

Space-Constructibility.

A functionS:ℕ→ℕS:\mathbb{N}\to\mathbb{N}isspace-constructibleif there exists a TM that, on input1n1^{n}, computesS​(n)S(n)in binary usingO​(S​(n))O(S(n))space. Common functions likenn,n2n^{2},2n2^{n}are space-constructible.

J.4Least-Fixpoint Semantics for Recursive Agentic Systems

We now give the formal construction of the semantics for a recursive agentic system(𝒮,ℱ)(\mathcal{S},\mathcal{F})where𝒮=(S1,…,Sm)\mathcal{S}=(S_{1},\ldots,S_{m})are scaffolds andℱ=(f1,…,fk)\mathcal{F}=(f_{1},\ldots,f_{k})are generators. Each scaffoldSiS_{i}may issue𝖦𝖤𝖭ℓ\mathsf{GEN}_{\ell}queries forℓ∈{1,…,k}\ell\in\{1,\ldots,k\}and𝖲𝖤𝖫𝖥j\mathsf{SELF}_{j}queries forj∈{1,…,m}j\in\{1,\ldots,m\}. The former are interpreted by the known functionsfℓf_{\ell}; the latter are interpreted by the unknown partial functions being defined.

Partial Functions and Order.

LetΣ⊥∗=Σ∗∪{⊥}\Sigma^{*}_{\bot}=\Sigma^{*}\cup\{\bot\}, where⊥\botdenotes “undefined.” This is a meta-level marker, not a string returned to or observed by a scaffold. Let𝒫={F:Σ∗→Σ⊥∗}\mathcal{P}=\{F:\Sigma^{*}\to\Sigma^{*}_{\bot}\}be the set of partial functions. We order𝒫\mathcal{P}byextension:F⊑GF\sqsubseteq Giff for allx∈Σ∗x\in\Sigma^{*}, eitherF​(x)=⊥F(x)=\botorF​(x)=G​(x)F(x)=G(x). The pair(𝒫,⊑)(\mathcal{P},\sqsubseteq)forms a complete partial order with least element⊥𝒫\bot_{\mathcal{P}}(the everywhere-undefined function). For tuples, define𝒫(m)=(𝒫)m\mathcal{P}^{(m)}=(\mathcal{P})^{m}with componentwise order; the least element is⊥(m)=(⊥𝒫,…,⊥𝒫)\bot^{(m)}=(\bot_{\mathcal{P}},\ldots,\bot_{\mathcal{P}}).

One-Step Operator.

Define𝚽𝒮,ℱ:𝒫(m)→𝒫(m)\bm{\Phi}_{\mathcal{S},\mathcal{F}}:\mathcal{P}^{(m)}\to\mathcal{P}^{(m)}as follows. Given𝐅=(F1,…,Fm)∈𝒫(m)\mathbf{F}=(F_{1},\ldots,F_{m})\in\mathcal{P}^{(m)}, theii-th component𝚽𝒮,ℱ​(𝐅)i\bm{\Phi}_{\mathcal{S},\mathcal{F}}(\mathbf{F})_{i}is defined by simulatingSiS_{i}on inputx∈Σ∗x\in\Sigma^{*}. A query𝖦𝖤𝖭ℓ​(u)\mathsf{GEN}_{\ell}(u)is answered by the fixed generator valuefℓ​(u)f_{\ell}(u). A query𝖲𝖤𝖫𝖥j​(u)\mathsf{SELF}_{j}(u)is answered by the current approximationFj​(u)F_{j}(u)if this value is defined. If the simulation does not halt, or if it queries someFj​(u)=⊥F_{j}(u)=\bot, the operator value is⊥\bot; in the latter case the scaffold is not given⊥\botas an oracle answer. If the simulation halts with outputyywithout making an undefined recursive query, then𝚽𝒮,ℱ​(𝐅)i​(x)=y\bm{\Phi}_{\mathcal{S},\mathcal{F}}(\mathbf{F})_{i}(x)=y.

ω\omega-Continuity and Existence.

The operator𝚽𝒮,ℱ\bm{\Phi}_{\mathcal{S},\mathcal{F}}isω\omega-continuous (Scott-continuous) on the pointed CPO(𝒫(m),⊑)(\mathcal{P}^{(m)},\sqsubseteq): each scaffold execution, if it terminates, makes only finitely many recursion queries, hence depends only on a finite stage of any increasing chain of approximants. By Kleene’s fixed-point theorem, the least fixpoint𝐅∗=lfp​(𝚽𝒮,ℱ)=⨆n<ω𝚽𝒮,ℱn​(⊥(m))∈𝒫(m)\mathbf{F}^{*}=\mathrm{lfp}(\bm{\Phi}_{\mathcal{S},\mathcal{F}})=\bigsqcup_{n<\omega}\bm{\Phi}_{\mathcal{S},\mathcal{F}}^{n}(\bot^{(m)})\in\mathcal{P}^{(m)}exists.

Semantics.

The semantics of the system(𝒮,ℱ)(\mathcal{S},\mathcal{F})is the least fixpoint𝐅∗=(F1∗,…,Fm∗)\mathbf{F}^{*}=(F_{1}^{*},\ldots,F_{m}^{*}). We identify the induced functions in the main text with these components, i.e.,ϕi𝒮,ℱ:=Fi∗\phi_{i}^{\mathcal{S},\mathcal{F}}:=F_{i}^{*}. Thusϕi𝒮,ℱ​(x)\phi_{i}^{\mathcal{S},\mathcal{F}}(x)is the output of running scaffoldSiS_{i}on inputxx, where𝖦𝖤𝖭ℓ\mathsf{GEN}_{\ell}is interpreted byfℓf_{\ell}and all𝖲𝖤𝖫𝖥j\mathsf{SELF}_{j}calls are resolved by the least fixpoint. If the generators inℱ\mathcal{F}are computable, then the induced functionsϕi𝒮,ℱ\phi_{i}^{\mathcal{S},\mathcal{F}}are ordinary partial computable functions; for arbitrary generators, they are partial computable relative to the generator oracles.

J.5Chandra–Kozen–Stockmeyer Characterization

Lemma 10(Alternating-space characterization of exponential time).

For any space-constructibleS​(n)≥nS(n)\geq n,𝖠𝖲𝖯𝖠𝖢𝖤​(O​(S​(n)))=𝖳𝖨𝖬𝖤​(2O​(S​(n)))\mathsf{ASPACE}(O(S(n)))=\mathsf{TIME}(2^{O(S(n))}).

Proof.

This is a classical result. The key insight is that an alternating TM using spaceSShas at most2O​(S)2^{O(S)}configurations, and a deterministic simulation can explore the entire game tree in time2O​(S)2^{O(S)}via dynamic programming. ∎

Appendix KProof of Theorem4

Proof ofTheorem˜4.

Fixnn, an indexr∈{1,…,m}r\in\{1,\ldots,m\}, and inputx∈Σnx\in\Sigma^{n}, and writeL:=L​(n)L:=L(n)andD:=Σ≤LD:=\Sigma_{\leq L}. Let𝚽𝒮,ℱ\bm{\Phi}_{\mathcal{S},\mathcal{F}}be the one-step operator from AppendixJ.4. UnderLL-boundedness (Definition4) of the evaluation ofϕr𝒮,ℱ​(x)\phi_{r}^{\mathcal{S},\mathcal{F}}(x), every generator argument/return and every recursion argument/return that appears during evaluation lies inDD. ThisLL-boundedness assumption counts query and answer strings held by a scaffold, whereas the standard relativized space measure for oracle Turing machines in§\mathsection˜J.3counts only work tapes.

Time upper bound (oracle form).

Let𝚽𝒮,ℱ(≤L)\bm{\Phi}^{(\leq L)}_{\mathcal{S},\mathcal{F}}be the same one-step operator as𝚽𝒮,ℱ\bm{\Phi}_{\mathcal{S},\mathcal{F}}, except that each scaffold simulation is run with an explicitLL-space cutoff (counting work plus oracle tapes): if the simulation exceedsLLtotal tape cells, the corresponding approximant value is declared undefined, i.e., set to⊥\bot. Since the recursive call tree of the evaluation ofϕr𝒮,ℱ​(x)\phi_{r}^{\mathcal{S},\mathcal{F}}(x)isLL-bounded, this cutoff never triggers on any scaffold invocation that influencesϕr𝒮,ℱ​(x)\phi_{r}^{\mathcal{S},\mathcal{F}}(x), soϕr𝒮,ℱ​(x)\phi_{r}^{\mathcal{S},\mathcal{F}}(x)equals the stabilized(r,x)(r,x)entry of the least fixpoint of𝚽𝒮,ℱ(≤L)\bm{\Phi}^{(\leq L)}_{\mathcal{S},\mathcal{F}}.

We compute this least fixpoint by performing Kleene iteration on the finite restriction toDD. Define a table-valued sequence(ϕt)t≥0(\bm{\phi}_{t})_{t\geq 0}where eachϕt\bm{\phi}_{t}is a tuple of partial mapsD→D∪{⊥}D\to D\cup\{\bot\}(one component per scaffold), withϕ0=⊥(m)\bm{\phi}_{0}=\bot^{(m)}andϕt+1=𝚽𝒮,ℱ(≤L)​(ϕt)\bm{\phi}_{t+1}=\bm{\Phi}^{(\leq L)}_{\mathcal{S},\mathcal{F}}(\bm{\phi}_{t})restricted to inputs inDD. Because the restriction domain is finite and the order is by extension, each table entry can change at most once (from⊥\botto a defined value), so the sequence stabilizes after at mostm⋅|D|m\cdot|D|iterations.

To update one table entry, we simulate one one-step scaffold run on an inputq∈Dq\in D, answering generator/tool queries by oracle access toℱ\mathcal{F}and answering recursion queries𝖲𝖤𝖫𝖥j​(u)\mathsf{SELF}_{j}(u)by table lookup ofϕt\bm{\phi}_{t}. By construction of𝚽𝒮,ℱ(≤L)\bm{\Phi}^{(\leq L)}_{\mathcal{S},\mathcal{F}}, each such update halts withinexp⁡(O​(L))\exp(O(L))transitions and costsexp⁡(O​(L))\exp(O(L))time. There arem⋅|D|=2O​(L)m\cdot|D|=2^{O(L)}entries and at mostm⋅|D|=2O​(L)m\cdot|D|=2^{O(L)}iterations, so the total oracle-machine running time is2O​(L)2^{O(L)}. The stabilized table entry corresponding to(r,x)(r,x)equalsϕr𝒮,ℱ​(x)\phi_{r}^{\mathcal{S},\mathcal{F}}(x), proving𝖣𝖳𝖨𝖬𝖤ℱ​(2O​(L​(n)))\mathsf{DTIME}^{\mathcal{F}}(2^{O(L(n))}).

Eliminating the oracle.

Now assume additionally that each generator/tool inℱ\mathcal{F}is computable by a deterministic (non-oracle) TM in time2O​(L​(n))2^{O(L(n))}and work spaceO​(L​(n))O(L(n))on all queries of length at mostL​(n)L(n). We simulate the above oracle TM by a plain TM, replacing each oracle query by running the corresponding oracle-computing TM on the query string and writing its output back before resuming the simulation. Since the oracle TM runs for at most2O​(L​(n))2^{O(L(n))}steps, it makes at most2O​(L​(n))2^{O(L(n))}oracle queries. Thus the total time is2O​(L​(n))⋅2O​(L​(n))=2O​(L​(n))2^{O(L(n))}\cdot 2^{O(L(n))}=2^{O(L(n))}, proving𝖳𝖨𝖬𝖤​(2O​(L​(n)))\mathsf{TIME}(2^{O(L(n))}). ∎

Appendix LProof of Theorem5

Proof ofTheorem˜5.

Fix an indexr∈{1,…,m}r\in\{1,\ldots,m\}. Assume the recursion stack depth isD​(n)=O​(1)D(n)=O(1)throughout evaluation ofϕr𝒮,ℱ​(x)\phi_{r}^{\mathcal{S},\mathcal{F}}(x)on every length-nninputxx. We decide the language by directly simulating the recursive evaluation in a depth-first manner on an oracle TM with access toℱ\mathcal{F}. The simulator maintains the full local configuration of the currently active scaffold simulation (including its work tapes and the bounded oracle query/answer content), and pushes/pops such configurations on a stack when encountering recursive scaffold calls and returns. ByL​(n)L(n)-boundedness, each call frame requiresO​(L​(n))O(L(n))space to store, and by assumption there areO​(1)O(1)frames simultaneously. Thus the simulation usesO​(L​(n))O(L(n))work space, proving membership in𝖣𝖲𝖯𝖠𝖢𝖤ℱ​(O​(L​(n)))\mathsf{DSPACE}^{\mathcal{F}}(O(L(n))).

Eliminating the oracle.

Now assume additionally that each generator/tool inℱ\mathcal{F}is computable by a deterministic (non-oracle) TM in time2O​(L​(n))2^{O(L(n))}and work spaceO​(L​(n))O(L(n))on all queries of length at mostL​(n)L(n). We simulate the above oracle TM by a plain TM, replacing each oracle query by running the corresponding oracle-computing TM on the query string and then resuming the simulation. ReusingO​(L​(n))O(L(n))work space for each oracle computation, the overall work space remainsO​(L​(n))O(L(n)), proving𝖣𝖲𝖯𝖠𝖢𝖤​(O​(L​(n)))\mathsf{DSPACE}(O(L(n))). ∎