Recursive Language Models Meet Uncertainty: The Surprising Effectiveness of Self-Reflective Program Search for Long Context
Problem Statement
Even with extended context windows, LLMs often fail to reliably extract and reason over information spread across long inputs. Agentic approaches like RLM decompose the context through programmatic recursive sub-calls, but how the interaction programs get selected has been largely unexplored, and RLM can underperform the base model on contexts that already fit in the window. RLM also struggles on semantically intensive tasks, where heuristic program search cannot capture the global contextual understanding the task needs.
Key Novelty
- SRLM: a framework that treats long-context handling as a search over context-interaction programs, guided by the model's intrinsic uncertainty signals.
- Combines three complementary uncertainty indicators (self-consistency across samples, reasoning-trace length, and verbalized confidence) as a training-free selection criterion for candidate programs.
- An empirical finding that recursion is not the primary driver of RLM's gains: simple self-reflective program search matches or beats RLM without explicit recursion or self-query.
- A diagnostic analysis showing that RLM degrades performance within the native context window and on semantically intensive tasks, while SRLM gives consistent gains in both regimes.
Evaluation Highlights
- Up to 22% improvement over RLM under the same inference time budget, across diverse benchmarks, context lengths, and backbone models.
- SRLM yields consistent gains over the base model for both short (within-window) and long contexts, whereas RLM with recursion often degrades performance at within-window lengths.
- SRLM's advantage over RLM is more pronounced on semantically intensive tasks requiring broad contextual understanding.
Signal Assessment
Methodology
- Frame long-context QA/reasoning as programmatic interaction: the LLM writes code (e.g., in a REPL-like environment) to inspect, slice, search, and query the long context instead of reading it all at once.
- Sample multiple candidate context-interaction programs and execution trajectories, each producing a candidate answer.
- Compute intrinsic uncertainty signals for each candidate: agreement with other candidates (self-consistency), length of the reasoning trace (longer often signals uncertainty or struggle), and the model's verbalized confidence.
- Let the model self-reflect using these signals to compare candidates and select the most reliable program/answer, optionally without recursive sub-calls or self-query.
- Evaluate against RLM and base models under matched time budgets across benchmarks, context lengths, and backbones.
System Components
The LLM generates executable programs that access and manipulate the long context (search, chunking, filtering) instead of consuming it directly in the prompt.
Generates multiple alternative context-interaction programs and trajectories so they can be compared, replacing single-shot or heuristic program selection.
Measures agreement among answers from different candidate programs; higher consensus indicates lower uncertainty.
Uses the length of the reasoning trace as an implicit uncertainty proxy, with unusually long traces suggesting confusion or low confidence.
Prompts the model to explicitly state its confidence in a candidate answer, providing a semantic self-assessment.
Aggregates the three uncertainty signals so the model can evaluate and rank candidate programs and pick the final answer.
Results
| Metric/Benchmark | Baseline | This Paper | Delta |
|---|---|---|---|
| Accuracy vs. RLM (same time budget, best case) | RLM | SRLM | Up to +22% |
| Within-window context lengths | RLM often below base model | SRLM consistently above base model | Qualitative: SRLM avoids RLM's degradation |
| Long contexts (beyond window) | RLM | SRLM | Consistent gains (qualitative) |
| Semantically intensive tasks | RLM (heuristic program search) | SRLM (self-reflective selection) | Larger margin in favor of SRLM (qualitative) |
| Need for recursion/self-query | Required in RLM | Not required in SRLM | Simpler pipeline with matched or better performance |
Key Takeaways
- For agentic long-context pipelines, invest in how you select among candidate interaction programs, for example with uncertainty-based reranking, before adding complex recursive sub-call machinery.
- Cheap, training-free uncertainty signals (self-consistency, trace length, verbalized confidence) combine well as a selector and can be added to existing code-executing agents with little engineering.
- Don't apply RLM-style recursion blindly when the input fits in the model's context window, since it can hurt performance relative to the base model. Gate decomposition on context length and task type.
- On semantically heavy tasks that need global understanding rather than lookup, heuristic programmatic search is insufficient. Use semantic self-reflection signals to steer reasoning.
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.