cs.CLMar 7, 2026

Recursive Language Models Meet Uncertainty: The Surprising Effectiveness of Self-Reflective Program Search for Long Context

Authors: Keivan Alizadeh, Parshin Shojaee, Minsik Cho, Mehrdad Farajtabar

Organizations: Apple

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Long-context handling remains a core challenge for language models: even with extended context windows, models often fail to reliably extract, reason over, and use the information across long contexts. Recent works like Recursive Language Models (RLM) have approached this challenge by agentic way of decomposing long contexts into recursive sub-calls through programmatic interaction at inference. While promising, the success of RLM critically depends on how these context-interaction programs are selected, which has remained largely unexplored. In this paper, we study this problem and introduce SRLM, a framework that augments programmatic context interaction with uncertainty-aware Self-Reflection. SRLM leverages three intrinsic signals: self consistency, reasoning length, and verbalized confidence. These serve as complementary indicators of a model's internal uncertainty, and the model uses them to evaluate and compare candidate context-interaction programs. Extensive experiments across diverse benchmark datasets, context lengths, and backbone models, show that SRLM consistently outperforms state-of-the-art baselines, yielding up to 22% improvement over RLM under the same time budget. Our findings show that recursion itself is not the primary driver of performance in RLM, and a simple self-reflective program search can match or surpass RLM without requiring self-query or explicit recursion mechanisms. We find that for context lengths within the model's window, RLMs with recursion often degrade performance relative to the base model, whereas SRLM yields consistent gains across both short and long contexts. We also find that RLM is less effective in tasks with semantically intensive nature, where heuristic program search is insufficient and broader contextual understanding is required, while self-reflection in SRLM provides a semantic signal that better steers reasoning in these scenarios.

Figures & tables

Figure 1: Overview of SRLM , a framework that augments programmatic context interaction reasoning with uncertainty-aware self-reflection. The language model operates in a self-query execution programming environment where the context is externalized as a variable, and generates programs that query and interact with context. Meanwhile, three complementary uncertainty signals (self-consistency, reasoning trace length, and verbalized confidence) are used to guide self-reflective programming trajectory selection without external supervision, enabling more robust and semantically grounded long-context reasoning.
ModelLongBench-v2 (CodeQA)BrowseComp+(1K)OOLONG (131K)
Task Length NN (tokens)23K-4.2M6M-11M131K
Qwen3-Coder-480B
Base Model20.0∗20.0^{*}0.0∗0.0^{*}36.036.0
CodeAct (+ BM25)24.0∗24.0^{*}12.712.738.038.0
CodeAct (+ sub-calls)26.0∗26.0^{*}0.00.032.032.0
Summary agent50.050.038.038.044.144.1
Table 1: Performance comparison of SRLM against baselines on long-context benchmarks from [ 75 ] . Results report accuracy (%) on LongBench-v2 CodeQA, BrowseComp+ (1K documents), and OOLONG (131K tokens). SRLM consistently outperforms all baselines, achieving up to 22% improvement over RLM. ∗ indicates context overflow; † indicates our replication of results; and bold shows best result per LLM backbone.
Figure 2: Performance across context lengths on OOLONG and LongBench-v2 Full datasets: Line plots show accuracy of SRLM , RLM, and the base LLM across context from thousands to millions of tokens using GPT-5 (left) and Qwen3-Coder-480B (right) backbones. Bar plots show the average performance gain over the base model, separated into contexts within ( <131{<}131 K) and near/beyond ( ≥131{\geq}131 K) the native context window.
Figure 3: Accuracy versus cost pareto comparison of RLM and SRLM (no sub-call) on long-context settings of benchmarks under GPT-5 ( left ) and Qwen3-Coder-480B ( right ).
Figure 4: Comparison of SRLM , RLM, and Base LLM across LongBench-v2 domains (averaged across backbone models). In general, SRLM variants show more consistent gains on tasks with different semantic nature.
Figure 5: Results of ablation experiments across SRLM ’s variants (averaged across backbones and recursive/nonrecursive runs). Top: Contribution of each uncertainty signal and their combination in SRLM . Bottom: Complementary effects of semantic and behavioral uncertainty as fine-grained signals guiding self-reflection in SRLM .
Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Distribution of input context lengths across different benchmarks: OOLONG, LongBench-v2, and BrowseComp-Plus.
Figure 7: Context length distributions for different task categories in LongBench-v2 benchmark dataset.
Figure 8: Performance gains over the base model across context lengths on the OOLONG benchmark. Bars show accuracy change vs. base for each context-length bin. Results are shown for GPT-5 ( top ) and Qwen3-Coder-480B ( bottom ). The shaded yellow region marks contexts near or beyond the context window limits ( ≥131\geq 131 K tokens).
Figure 9: Performance gains over the base model across context lengths on the LongBench-v2 benchmark. Bars show accuracy change vs. base for each context-length bin with balanced samples. Results are shown for GPT-5 ( top ) and Qwen3-Coder-480B ( bottom ) backbones. The shaded yellow region marks contexts near or beyond the context window limits ( ≥131\geq 131 K tokens).
Figure 10: Accuracy versus context length across LongBench-v2 task categories. Results for GPT-5 ( left ) and Qwen3-Coder-480B ( right ) backbones, with each subplot showing performance across context scales for a specific task domain.
Figure 11: Improvement over the base model across context lengths for LongBench-v2 task domains. Results for GPT-5 ( left ) and Qwen3-Coder-480B ( right ), with each subplot showing performance change across context scales for a specific task domain.
Figure 12: Ablation of uncertainty signals in SRLM ’s self-reflection mechanism. Results for GPT-5 and Qwen3-Coder-480B backbones on OOLONG, LongBench-v2, and BrowseComp+ (1K) benchmarks with context ≥131\geq 131 K. (a) With recursive sub-calls; (b) Without recursive sub-calls.
Figure 13: Analysis of the relationship between verbalized confidence, reasoning length, and accuracy. Heatmaps show accuracy across equal-sample bins of confidence (x-axis) and reasoning length (y-axis). Results are reported for GPT-5 and Qwen3-Coder-480B backbones on the OOLONG, LongBench-v2, and BrowseComp+ (1K) benchmarks with context ≥131\geq 131 K. (a) With recursive sub-calls; (b) Without recursive sub-calls.
More in this topic

Long-Context Language Model Inference

Long-context language model inference makes processing and generating over lengthy prompts faster and more memory-efficient.

See all 227 papers

Explore similar work

CardsList
Mar 20, 2026

The Y\mathbf{Y}-Combinator for LLMs: Solving Long-Context Rot with λλ-Calculus

LLMs are increasingly used as general-purpose reasoners, but long inputs remain bottlenecked by a fixed context window. Recursive Language Models (RLMs) address this by externalising the prompt and recursively solving subproblems. Yet existing RLMs depend on an open-ended read-eval-print loop (REPL) in which the model generates arbitrary control code, making execution difficult to verify, predict, and analyse. We introduce λλ-RLM, a framework for long-context reasoning that replaces free-form recursive code generation with a typed functional runtime grounded in λλ-calculus. It executes a compact library of pre-verified combinators and uses neural inference only on bounded leaf subproblems, turning recursive reasoning into a structured functional program with explicit control flow. We show that λλ-RLM admits formal guarantees absent from standard RLMs, including termination, closed-form cost bounds, controlled accuracy scaling with recursion depth, and an optimal partition rule under a simple cost model. Empirically, across four long-context reasoning tasks and nine base models, λλ-RLM outperforms standard RLM in 29 of 36 model-task comparisons, improves average accuracy by up to +21.9 points across model tiers, and reduces latency by up to 4.1x. These results show that typed symbolic control yields a more reliable and efficient foundation for long-context reasoning than open-ended recursive code generation. The complete implementation of λλ-RLM, is open-sourced for the community at: https://github.com/lambda-calculus-LLM/lambda-RLM.

Amartya Roy, Rasul Tutunov, Xiaotong Ji +2

The School of Interdisciplinary Research, Indian Institute of Technology (IIT) Delhi, Robert Bosch GmbH, India · Huawei Noah’s Ark Lab · Huawei Noah’s Ark +1

Long-Context Reasoning in Language ModelsLong-Context Language Model InferenceEfficient Language Model ReasoningRecursive Language Models
AskPDF
Mar 2, 2026

Recursive Models for Long-Horizon Reasoning

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.

Chenxiao Yang, Nathan Srebro, Zhiyuan Li

Toyota Technological Institute at Chicago

Recursive Language ModelsLanguage ModelingAlgorithmic ReasoningLLM ReasoningLong-Horizon ReasoningLong-Context Modeling+3
AskPDF
Mar 3, 2026

Think, But Don't Overthink: Reproducing Recursive Language Models

This project reproduces and extends the recently proposed Recursive Language Models'' (RLMs) framework by Zhang et al. (2026). This framework enables Large Language Models (LLMs) to process near-infinite contexts by offloading the prompt into an external REPL environment. While the original paper relies on a default recursion depth of 1 and suggests deeper recursion as a future direction, this study specifically investigates the impact of scaling the recursion depth. Using state-of-the-art open-source agentic models (DeepSeek v3.2 and Kimi K2), I evaluated pure LLM, RLM (depth=1), and RLM (depth=2) on the S-NIAH and OOLONG benchmarks. The findings reveal a compelling phenomenon: Deeper recursion causes models to overthink''. While depth-1 RLMs effectively boost accuracy on complex reasoning tasks, applying deeper recursion (depth=2) or using RLMs on simple retrieval tasks paradoxically degrades performance and exponentially inflates execution time (e.g., from 3.6s to 344.5s) and token costs. Code and data are available at: https://github.com/drbillwang/rlm-reproduction

Daren Wang

The Chinese University of Hong Kong

Recursive Language ModelsOverthinking in Language ModelsEfficient Language Model ReasoningLong-Context Language Model Evaluation
AskPDF