ReTreVal: Reasoning Tree with Validation - A Hybrid Framework for Enhanced LLM Multi-Step Reasoning

Abhishek Hs, Pavan C. Shekar, Arpit Jain, Ashwanth KrishnanarXiv 2026 · arXiv · OpenReview

TL;DR

This paper introduces ReTreVal, a novel framework that empowers Large Language Models (LLMs) to learn from their mistakes across different problems without any parameter updates. By combining tree-based reasoning with a unique "typed-failure backtracking" and a self-rewriting memory, ReTreVal significantly boosts LLM performance on complex reasoning tasks like math and logic problems.

What Problem Does This Paper Address?

LLMs often struggle with complex, multi-step reasoning tasks. While existing methods like ReAct, Reflexion, and Self-Refine offer ways to improve reasoning within a single problem (e.g., by reflecting on errors or iteratively refining solutions), they have a critical limitation: they forget everything about a failed attempt once a problem is over. This means an LLM tackling problem 500 is no wiser than when it started problem 1, despite potentially encountering hundreds of similar failures. The authors aim to bridge this gap by enabling LLMs to accumulate and utilize "typed failure experience" across a sequence of problems, leading to inference-time cross-problem learning without any retraining.

Methods

ReTreVal is a sophisticated framework built around several key innovations:

  • Adaptive Tree Construction: Instead of a fixed search depth, ReTreVal estimates problem complexity and dynamically adjusts the depth and branching factor of its reasoning tree. This prevents wasting computation on simple problems and allows deeper exploration for complex ones.
  • Tool-Augmented Refinement: At each step within the reasoning tree, ReTreVal can leverage an extensible registry of tools (like symbolic solvers or arithmetic evaluators) to verify intermediate computations. This is crucial for preventing cascading errors from incorrect calculations.
  • Typed-Failure Backtracking: When a reasoning path fails, ReTreVal doesn't just retry. It analyzes the failure, categorizes it by root cause (e.g., "arithmetic_error," "logic_error") and approach type, and injects this specific "typed failure context" into the critique history of sibling branches. This structurally prevents the same error class from recurring.
  • Self-Rewriting Memory: This is a core component for cross-problem learning. The memory stores insights from successful reasoning and failure patterns. When an entry accumulates enough "experience signals," the LLM rewrites the entry itself, updating its strategy for future problems without any weight changes.
  • Critique-Based Scoring with Skepticism: Nodes in the tree are scored based on self-evaluation and peer critique. A "skepticism penalty" is applied based on the historical reliability of different reasoning approaches, discouraging reliance on consistently underperforming strategies.
  • Task Decomposition: For highly complex problems, ReTreVal can break them down into smaller, dependency-ordered subtasks, each handled by a specialized sub-agent.

Datasets

The paper evaluates ReTreVal on two standard benchmarks:

  • MATH-500: A dataset of 500 competition-style math problems across 7 subjects and 5 difficulty levels.
  • MMLU-Pro: A more challenging version of the MMLU benchmark, featuring 1,000 problems with ten answer choices per question, spanning a wide range of quantitative and qualitative domains.

Key Insights and Ideas

  • Learning Without Retraining: The most significant insight is that LLMs can achieve meaningful cross-problem learning and strategy improvement solely at inference time, without any parameter updates or fine-tuning. This opens up new avenues for making LLMs more adaptable and efficient.
  • The Power of Specific Failure Context: Simply knowing a step failed isn't enough. Categorizing why it failed (e.g., "arithmetic error" vs. "logic error") and injecting that specific context into alternative paths is a powerful mechanism for preventing repeated mistakes.
  • Memory as a Dynamic Strategy Editor: The self-rewriting memory is a clever way to evolve an LLM's reasoning strategies over time. Instead of just storing past failures, the LLM actively refines its own internal "rules" or approaches based on accumulated experience.
  • Tool Verification is Key for Complex Math: For quantitative tasks, the ability to verify intermediate steps with external tools is critical. This eliminates a major source of errors that plague purely LLM-based reasoning.

Key Results

ReTreVal demonstrates significant improvements over strong baselines:

  • MATH-500: Achieves 85.8% accuracy, an +8.6 pp gain over Self-Refine. This advantage grows with problem difficulty, highlighting ReTreVal's strength in tackling complex reasoning.
  • MMLU-Pro: Achieves 54.4% accuracy, a substantial +15.3 pp gain over Self-Refine. This indicates its effectiveness across a broader range of subjects, including qualitative domains.
  • Win-to-Regression Ratio: A 3.4:1 ratio confirms that ReTreVal's improvements are due to genuine error recovery rather than random chance.
  • Computational Cost: ReTreVal uses roughly 2.3x the tokens of Self-Refine for its accuracy gains, with overhead concentrated on harder problems where the gains are largest.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • Computational Overhead: For latency-sensitive applications, the computational cost on hard problems might be prohibitive.
  • Complexity Estimator: The complexity estimator can occasionally over-budget simple problems, leading to unnecessary computation and even regressions. A short-circuit rule for high-confidence single-shot answers is suggested.
  • Backtracking Scope: Backtracking is currently limited to root-level children. Deeper backtracking could potentially recover more failures.
  • Critique Mechanism: Single-model critique might introduce correlated errors. Exploring decoupled critic models is a future direction.
  • Deduplication: Keyword-Jaccard deduplication might miss semantically similar insights in the memory.
  • Future Work: The authors propose exploring adaptive budgets for backtracking, embedding-based memory deduplication, decoupled critic models, and early-exit mechanisms for simple problems.

Summary updated

Abstract

Multi-step reasoning remains a key challenge for Large Language Models (LLMs), particularly in complex domains such as mathematics and creative writing. While recent approaches including ReAct, Reflexion, and Self-Refine improve reasoning through iterative refinement and reflection, they often lack structured exploration of alternative solution paths and persistent learning across problems. We propose ReTreVal (Reasoning Tree with Validation), a hybrid framework that integrates Tree-of-Thoughts exploration, self-refinement, LLM-based critique scoring, and reflexion memory to enable bounded and validated multi-step reasoning. ReTreVal constructs a structured reasoning tree with adaptive depth based on problem complexity, where each node undergoes iterative self-critique and refinement guided by explicit LLM-generated feedback. A dual validation mechanism evaluates reasoning quality, coherence, and correctness at each node while persistently storing insights from successful reasoning paths and failure patterns in a reflexion memory buffer, enabling cross-problem learning. Critique-based pruning retains only the top-k highest-scoring nodes at each level, controlling computational cost while preserving high-quality solution paths. We evaluate ReTreVal against ReAct, Reflexion, and Self-Refine across 500 mathematical problems and creative writing tasks using Qwen 2.5 7B as the underlying LLM, and demonstrate that ReTreVal consistently outperforms existing methods through its combination of structured exploration, critique-driven refinement, and cross-problem memory, making it particularly effective for tasks requiring exploratory reasoning, rigorous verification, and knowledge transfer.
BibTeX
@misc{hs2026retreval,
  author = {Abhishek HS and Pavan C. Shekar and Arpit Jain and Ashwanth Krishnan},
  title = {{ReTreVal: Reasoning Tree with Validation - A Hybrid Framework for Enhanced LLM Multi-Step Reasoning}},
  year = {2026},
  eprint = {2601.02880},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.02880},
}
Figure