PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Keivan Alizadeh, Parshin Shojaee, Minsik Cho, Mehrdad Farajtabar

arXiv:2603.15653v1cs.CLcs.AIcs.LG

TL;DR

Long-context models still struggle to reliably use information across extended inputs, and the selection of context-interaction programs in recursive approaches remains underexplored. SRLM applies self-reflection using three intrinsic uncertainty signals to compare candidate programs. Across diverse settings, it consistently improves performance, achieving up to 22% over RLM, while showing that recursion alone is not the primary driver.

  • Problem

    Long-context models struggle to extract, integrate, and reason over distant information, while how recursive context-interaction programs should be selected remains underexplored.

  • Method

    SRLM uses self-consistency, reasoning trace length, and verbalized confidence to guide self-reflective comparison and selection of candidate context-interaction programs.

  • Results

    SRLM consistently improves performance across diverse benchmarks, context lengths, and backbone models, achieving up to 22% improvement over RLM under the same time budget.

  • Takeaways & Limitations

    Self-reflective program search can match or surpass RLM without explicit recursion or self-query mechanisms and remains effective across short, long, and semantically demanding contexts.

  • Takeaways & Limitations

    The paper uses a relatively simple intrinsic self-reflection design, leaving richer reflection and earlier reasoning termination for future work.

Abstract

from arXiv · show

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.

1 Introduction

Long-context reasoning remains difficult despite larger context windows, motivating programmatic context interaction and uncertainty-aware selection of reasoning trajectories. SRLM uses self-reflection to improve this selection, outperform RLM by up to 22%, and reveals that recursion is not the primary performance driver.

  • Long-context models can lose salient details, fail to integrate distant information, and become distracted by irrelevant content as context length grows.
  • RLM performance depends on selecting effective context-interaction programs, but fixed recursion schemes lack a principled way to compare alternative reasoning trajectories.
  • SRLM uses self-consistency, reasoning trace length, and verbalized confidence to compare and select context-interaction trajectories through self-reflection.
  • 22% improvement over RLM is achieved across diverse benchmarks and backbone models under the same wall-clock time budget.
  • Recursion is not the primary driver of RLM performance because simple self-reflective program search can match or surpass recursive approaches without explicit self-query mechanisms.
  • RLM often performs worse than the base model within its native context window, whereas SRLM improves more consistently across short and long contexts and semantically intensive tasks.

2 Methodology

SRLM treats long-context reasoning as search over executable context-interaction programs rather than dependence on explicit recursion. It compares candidate trajectories using self-consistency, verbalized confidence, and reasoning length as complementary uncertainty signals.

  • 2.1 Problem Formulation: SRLM represents a long context as an external variable and executes autoregressively generated programs that slice, query, or aggregate it.Each program produces intermediate execution states and a terminal answer; explicit recursive self-queries are optional.
  • 2.2 Self-Reflective Program Search: Candidate programs are independently sampled from the model policy, producing distinct trajectories over inspected segments, decompositions, and intermediate conclusions.The search compares these trajectories rather than assuming one fixed reasoning path.
  • 2.2.1 Uncertainty Signals: Self-consistency estimates answer confidence from empirical frequencies across independently sampled programs and retains programs agreeing with the plurality answer.This provides implicit verification but operates only at the final-output level.
  • 2.2.1 Uncertainty Signals: Verbalized confidence aggregates the model’s step-level self-assessments across a trajectory, with values closer to zero indicating higher global confidence.The signal captures semantic uncertainty in intermediate reasoning rather than only final-answer agreement.
  • 2.2.1 Uncertainty Signals: Reasoning length serves as an implicit epistemic-effort signal, with longer traces interpreted as more deliberative and complementary to self-reported confidence.Unlike verbalized confidence, it requires no explicit elicitation and uses observable generation statistics.
  • 2.2.1 Uncertainty Signals: Combining self-consistency, verbalized confidence, and trace length provides a richer uncertainty characterization for guiding program search than any individual signal alone.The three signals target sampling-based, semantic, and behavioral aspects of uncertainty.

3 Experiments

The experiments evaluate SRLM across diverse long-context tasks, backbone models, and context lengths against task-agnostic inference-time baselines. The reported comparisons emphasize accuracy, fair wall-clock budgets, and the roles of recursion and programmatic context interaction.

  • 3.1 Datasets: SRLM is evaluated on BrowseComp+ (1K), OOLONG (131K), and LongBench-v2 CodeQA, covering multi-document QA, chunk transformation and aggregation, and code-repository understanding.Extended OOLONG evaluations span approximately 1K to 4M tokens.
  • 3.2 Baselines: The comparison includes base-model prompting, BM25-equipped CodeAct, CodeAct with sub-calls, summary agents, and recursive or non-recursive RLM variants.Baselines use the same backbone models and sampling parameters for each comparison.
  • 3.3 Experimental Setup: The experiments use Qwen3-Coder-480B-A35B and GPT-5 backbones, with GPT-5-mini used for recursive calls.SRLM and RLM operate in the same REPL environment.
  • 3.3 Experimental Results: SRLM consistently outperforms all baselines, achieving up to 22% improvement over RLM on benchmark accuracy.Table 1 reports accuracy on CodeQA, BrowseComp+ (1K documents), and OOLONG (131K tokens).
  • 3.3 Experimental Results: The table marks context overflow with ∗, replicated results with †, and the best result for each backbone in bold.These annotations qualify the reported accuracy comparisons.

3.4 Main Results

SRLM consistently outperforms RLM across long-context benchmarks and can outperform recursive program search at comparable or lower cost. Recursion helps inconsistently across backbones, while self-reflection provides more stable gains.

  • Up to 22% improvement over RLM is achieved by SRLM across long-context benchmarks and both backbone models.
  • SRLM provides stable improvements across GPT-5 and Qwen3-Coder-480B, even without recursive sub-calls.
  • Recursion helps Qwen3-Coder-480B but usually hurts GPT-5, whose nonrecursive variants outperform recursive counterparts in most cases.
  • Self-reflection can outperform recursion in both accuracy and wall-clock cost under long-context settings.All trajectories execute in parallel, so SRLM’s wall-clock time does not significantly exceed RLM’s.

3.7 Task Semantics and Limits of Recursion

Recursion’s value depends strongly on task semantics: it helps structured search tasks more than semantically demanding tasks. SRLM’s uncertainty signals and self-reflection provide broader, more consistent guidance.

  • SRLM variants show more consistent gains across LongBench-v2 domains with different semantic natures.
  • Recursion is more effective for structured tasks such as Code QA and Structured Data QA than for Dialogue History QA and Document QA.
  • The ablations combine self-consistency, verbalized confidence, and reasoning-trace length as complementary uncertainty signals.

4 Related Works

Related work addresses long-context reasoning through context-window expansion, architectural and training changes, agentic inference-time interaction, and dedicated evaluation benchmarks. Confidence estimation supplies uncertainty signals relevant to self-reflection.

  • Context-window research expands maximum input length through positional-encoding, attention-scaling, sparsity, state-space, retrieval, and cache-compression approaches.
  • Agentic long-context methods treat context handling as procedural interaction with language models invoked through programmatic strategies.
  • Long-context benchmarks evaluate realistic documents, dialogues, and codebases while exposing performance degradation as context length increases.
  • Confidence-estimation work uses sampling agreement and verbalized confidence to estimate uncertainty without additional fine-tuning.

5 Conclusion

The paper presents SRLM as evidence that self-reflective program search can improve long-context reasoning more consistently than recursion alone. It also identifies richer self-reflection and better token-use control as open directions.

  • SRLM uses self-consistency, reasoning-trace length, and verbalized confidence to guide context-interaction programs.
  • Up to 22% gains over RLM are reported across diverse benchmarks, context lengths, and backbone models.
  • SRLM improves both long contexts and shorter contexts within the model window, where RLM can hurt performance.
  • The paper’s relatively simple intrinsic self-reflection design is an acknowledged limitation and motivates richer future approaches.

A Details on Datasets

The evaluation uses three complementary long-context benchmarks spanning information aggregation, realistic reasoning and comprehension, and tool-assisted deep research. Their contexts range from 1K to millions of tokens, enabling comparisons across substantially different context lengths.

  • BrowseComp-Plus: BrowseComp-Plus evaluates deep-research agents answering complex fact-seeking questions that require combining evidence across multiple sources.Its fixed document corpus separates retrieval failures from reasoning failures and supports reproducible experiments.
  • OOLONG: OOLONG evaluates large-scale information aggregation rather than only sparse retrieval, covering 650 tasks from 1K to 8M tokens.Numeric outputs receive exponential partial credit, while categorical outputs use exact match or judge-based equivalence.
  • Context distributions: Figure 6 summarizes the input context-length distributions for OOLONG, LongBench-v2, and BrowseComp-Plus.These distributions characterize the context scales represented across the evaluation benchmarks.
  • LongBench-v2: LongBench-v2 evaluates reasoning and comprehension over realistic long contexts using standardized A/B/C/D multiple-choice tasks.It contains 503 instances with contexts ranging from 8K to 4M tokens.

B Prompt Details

The appendix specifies how verbalized confidence is elicited during candidate-program generation and how final answers are judged. Prompts enforce parseable, consistent confidence reports, while an LLM judge evaluates semantic equivalence rather than exact wording.

  • B.1 Verbalized Confidence Elicitation: At every intermediate generation step, SRLM elicits each candidate program’s self-assessed confidence.A fixed structured instruction is appended to the generation prompt.
  • B.1 Verbalized Confidence Elicitation: The confidence instruction requires a parseable score and consistent formatting across all generation steps and candidate programs.It also encourages nuanced and calibrated rather than coarse or overconfident reporting.
  • B.1 Verbalized Confidence Elicitation: If a model omits verbalized confidence, SRLM fills the gap with the average confidence from other steps in the same trajectory.This fallback applies only to rare missing-confidence cases.
  • B.1 Verbalized Confidence Elicitation: Confidence is reported as a JSON number between 0.000 and 100.000 with up to three decimal points.The instruction requires the score on a new line at the end of the response.
  • B.2 Evaluation Judge: Final task accuracy is evaluated with an LLM-as-Judge procedure because semantically correct answers can differ textually.The judge compares generated responses with ground-truth answers rather than relying solely on exact string matching.
  • B.2 Evaluation Judge: The judge prompt supplies the question, response, and correct answer, then requires a structured judgment format.Its fields include the extracted final answer, repeated correct answer, reasoning, and correctness decision.
  • B.2 Evaluation Judge: The judge accepts string variations, additional correct detail, and small numerical errors when determining semantic equivalence.It returns “yes” only when the extracted answer matches or falls within the permitted margin.

C.1 Detailed Results Across Context Lengths

The context-length analysis examines performance trends in finer-grained bins than the main results. SRLM’s gains become more pronounced as contexts lengthen, while RLM often underperforms the base model when contexts fit within the model window.

  • Context-length trends: The appendix breaks aggregated context-length results into finer-grained bins and task categories for OOLONG and LongBench-v2.Figures 8–11 show how methods behave as input context grows.
  • Context-length trends: SRLM’s improvement over the base model increases as context length grows across both benchmarks and both backbone models.The gains become more pronounced at longer contexts.
  • Context-length trends: RLM mostly underperforms the base model at shorter context lengths.The analysis attributes this pattern to possible overhead from recursive decomposition when the context already fits within the model window.
  • Task-domain analysis: Across code repository understanding, single-document question answering, multi-document question answering, and long in-context learning, SRLM’s benefits remain consistent.Improvements become more pronounced near or beyond the underlying model’s context-window limits.

C.2 Detailed Ablation Results

The ablation analysis evaluates SRLM’s uncertainty signals across backbones, datasets, and recursive settings. The full combination performs best for contexts of at least 131K tokens, although individual signal strength varies by dataset and backbone.

  • Ablation setup: The appendix separates ablation results by backbone model, dataset, and execution setting.These analyses examine how individual uncertainty signals contribute under different conditions.
  • Signal ablations: Across datasets and backbones, the full SRLM configuration consistently achieves the best performance.Variants using individual uncertainty signals alone show smaller improvements for queries with context length ≥131K.
  • Signal ablations: The three uncertainty signals provide complementary information about model uncertainty during reasoning.Reasoning trace length is stronger on some datasets, whereas verbalized confidence is more informative on others when calibration is reliable.
  • Task-domain analysis: Figures 10 and 11 organize LongBench-v2 results by task domain, showing absolute accuracy and improvement relative to the base model across context lengths.The plots cover GPT-5 and Qwen3-Coder-480B backbones.
  • Signal ablations: Figure 12 compares uncertainty-signal ablations on OOLONG, LongBench-v2, and BrowseComp+ (1K) for contexts ≥131K tokens.It reports GPT-5 and Qwen3-Coder-480B with and without recursive sub-calls.
  • Signal analysis: Figure 13 relates verbalized confidence and reasoning length to accuracy using equal-sample-bin heatmaps.Results are shown with and without recursive sub-calls for both backbones on three benchmarks with context ≥131K.
Loading 2603.15653v1…