Recursive Models for Long-Horizon Reasoning

Abstract

Modern language models reason within bounded attention size, a physical 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 sequences that are contextually isolated. We prove that any computable problem admits a recursive decomposition where subtasks require only exponentially smaller active context than standard autoregressive models, and this approach strictly surpasses any single-context management approaches such as summarization. We further show that modern agentic systems are naturally suited for realizing recursion in a generalized way where arbitrary processing of contexts and workflows is allowed, and prove they can achieve the same power as recursive models, yet none can surpass it. Experimentally, we train a 3B model to learn recursive reasoning and evaluate on SAT, finding that it significantly outperforms frontier LLMs.