Recursive Language Models Through the Admissibility-Dynamics Framework: A Principled Theory of When Recursive Scaffolding Succeeds

Theoretical analysis of Recursive Language Models (RLMs) through the admissibility-dynamics framework. Establishes three structural results — RLM sufficiency, insufficiency, and accumulation — that recover the empirical performance pattern from Zhang et al. as structural consequences of the architectural information bound, position their six baselines within a mitigation taxonomy, and generate thirteen novel predictions (three testable against existing data, ten requiring new benchmarks). Abstract Recursive Language Models (RLMs), recently introduced by Zhang et al., achieve striking empirical gains on long-context tasks by treating the input prompt as an external REPL environment and allowing the underlying language model to recursively decompose and process the prompt through programmatically constructed sub-calls. On the OOLONG-Pairs benchmark, where base GPT-5 and base Qwen3-Coder-480B each attain F1 scores of 0.1%, the corresponding RLM variants attain 58.0% and 23.1% respectively. The existing RLM literature lacks a principled theoretical account of when this recursive scaffolding will succeed and when it will fail. We provide such an account by applying the admissibility-dynamics framework of the preceding papers in this program (PIT, NEO, IA, HAL) to RLM architectures. We formalize the RLM as a structured tuple with explicit execution-trace semantics, and give a formal definition of faithful summary construction as the proof obligation for summary-state escape in the RLM setting. Within this formalization, we establish three structural results under the formal RLM execution model. First (Theorem 1, Sufficiency), the architecture satisfies the constraint requirement for a constraint class C if and only if C admits a bounded-slice decomposition, a faithful summary decoder exists in the sense we make precise, and the root model can orchestrate the decomposition from its bounded projection alone. Second (Theorem 2, Insufficiency), constraint classes whose certification depth exceeds the information bound B(c, K, m, d, I) = Ic + Imb·β(K, m, d) derived in the information-bound lemma — with β(K, m, d) ≤ m^(d−1) capturing the combinatorial scaling of recursion depth — lie outside the architecture's reach; no RLM with those parameters can satisfy the constraint requirement on those classes. Third (Theorem 3, Accumulation), for conjunctively decomposable constraints, the expected residual failure count across N sub-calls admits a policy-independent lower bound N / |U_M| that inherits from IA Theorem 1 and explains the high-variance trajectories observed in Zhang et al.'s experiments. These results recover Zhang et al.'s Table 1 performance pattern as structural consequences, position their six baselines within a mitigation taxonomy that predicts the reach of each, and extend beyond their tested benchmarks to make thirteen novel predictions — three testable against Zhang et al.'s existing data, ten requiring new benchmarks, for which we specify concrete designs. The underlying impossibility and sufficiency results are machine-checked in Lean 4 in the companion papers; the correspondence is recorded in the appendix. The contribution is complementary to and grounding for the empirical RLM research direction, not in competition with it. Companion Lean 4 formalization: https://doi.org/10.5281/zenodo.20060154 GitHub repository: https://github.com/shawnjason/Recursive-Language Related papers in the program: PIT (foundational projection-theoretic result): https://doi.org/10.5281/zenodo.19633241NEO (forward-case impossibility theorem): https://doi.org/10.5281/zenodo.19688367IA (admissibility-dynamics framework applied here to RLM architectures): https://doi.org/10.5281/zenodo.19688628HAL (language-model specialization providing the structural-ceiling context): https://doi.org/10.5281/zenodo.19715059OOL (OOLONG-Pairs empirical companion testing the predictions of this paper): https://doi.org/10.5281/zenodo.20277804SUD (Sudoku-Microscope empirical validation): https://doi.org/10.5281/zenodo.20277939HAM (Hamiltonian-Microscope cross-provider pilot): https://doi.org/10.5281/zenodo.20278073