# Recursive Models for Long-Horizon Reasoning

arXiv: https://arxiv.org/abs/2603.02112 · HTML: https://mlsanity.com/paper/2603.02112/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 35 of its 65 references that are in the map.
- First posted on arXiv 2 Mar 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 35)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [ReAct: Synergizing Reasoning and Acting in Language Models](https://mlsanity.com/paper/2210.03629/) (2022)
- [Reflexion: Language Agents with Verbal Reinforcement Learning](https://mlsanity.com/paper/2303.11366/) (2023)
- [Generative Agents: Interactive Simulacra of Human Behavior](https://mlsanity.com/paper/2304.03442/) (2023)
- [A Survey on Large Language Model based Autonomous Agents](https://mlsanity.com/paper/2308.11432/) (2023)
- [MetaGPT: Meta Programming for A Multi-Agent Collaborative Framework](https://mlsanity.com/paper/2308.00352/) (2023)
- [Structured Denoising Diffusion Models in Discrete State-Spaces](https://mlsanity.com/paper/2107.03006/) (2021)
- [CAMEL: Communicative Agents for "Mind" Exploration of Large Language Model Society](https://mlsanity.com/paper/2303.17760/) (2023)
- [A-MEM: Agentic Memory for LLM Agents](https://mlsanity.com/paper/2502.12110/) (2025)
- [Simple and Effective Masked Diffusion Language Models](https://mlsanity.com/paper/2406.07524/) (2024)
- [Mem0: Building Production-Ready AI Agents with Scalable Long-Term Memory](https://mlsanity.com/paper/2504.19413/) (2025)
- [Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution](https://mlsanity.com/paper/2310.16834/) (2023)
- [Simplified and Generalized Masked Diffusion for Discrete Data](https://mlsanity.com/paper/2406.04329/) (2024)
- [Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective](https://mlsanity.com/paper/2305.15408/) (2023)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [MemAgent: Reshaping Long-Context LLM with Multi-Conv RL-based Memory Agent](https://mlsanity.com/paper/2507.02259/) (2025)
- [MEM1: Learning to Synergize Memory and Reasoning for Efficient Long-Horizon Agents](https://mlsanity.com/paper/2506.15841/) (2025)
- [Memory-R1: Enhancing Large Language Model Agents to Manage and Utilize Memories via Reinforcement Learning](https://mlsanity.com/paper/2508.19828/) (2025)
- [ADaPT: As-Needed Decomposition and Planning with Language Models](https://mlsanity.com/paper/2311.05772/) (2023)
- [Dynamic Cheatsheet: Test-Time Learning with Adaptive Memory](https://mlsanity.com/paper/2504.07952/) (2025)
- [Agent S2: A Compositional Generalist-Specialist Framework for Computer Use Agents](https://mlsanity.com/paper/2504.00906/) (2025)
- [Scaling Long-Horizon LLM Agent via Context-Folding](https://mlsanity.com/paper/2510.11967/) (2025)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Recursive Language Models](https://mlsanity.com/paper/2512.24601/) (2025)
- [Learning Adaptive Parallel Reasoning with Language Models](https://mlsanity.com/paper/2504.15466/) (2025)
- [EvoFlow: Evolving Diverse Agentic Workflows On The Fly](https://mlsanity.com/paper/2502.07373/) (2025)
- [X-MAS: Towards Building Multi-Agent Systems with Heterogeneous LLMs](https://mlsanity.com/paper/2505.16997/) (2025)
- [PENCIL: Long Thoughts with Short Memory](https://mlsanity.com/paper/2503.14337/) (2025)

## Built on by (most cited first, 9 of 9)

- [Pseudo-Formalization for Automatic Proof Verification](https://mlsanity.com/paper/2605.20531/) (2026)
- [The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought](https://mlsanity.com/paper/2607.07423/) (2026)
- [Quantizing Recursive Reasoning Models](https://mlsanity.com/paper/2607.16237/) (2026)
- [The Complexity Ceiling Benchmark: A Multi-Domain Evaluation of Sequential Reasoning Under Depth Scaling](https://mlsanity.com/paper/2606.29278/) (2026)
- [Hierarchical Domain Generalization](https://mlsanity.com/paper/2607.16528/) (2026)
- [ThinkReset: Learnable Intermediate Interface Construction for Bounded-Context Long-Horizon Reasoning](https://mlsanity.com/paper/2607.28642/) (2026)
- [Recursive Vision Language Models for General Symbolic Reasoning](https://mlsanity.com/paper/2608.01534/) (2026)
- [Recursive Agentic Reasoning](https://mlsanity.com/paper/2608.23956/) (2026)
- [Recursive Language Models Generalize Out of Domain](https://mlsanity.com/paper/2609.20831/) (2026)

## Abstract (arXiv)

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.