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