acceptodds
Under review as a conference paper at ICLR 2027

ReTreVal: Reasoning Tree with Validation and Cross-Problem Memory for Large Language Models

Abstract

Every existing inference-time reasoning framework discards failure context at problem boundaries, leaving a model solving problem 500 no wiser than it was on problem 1. We present ReTreVal (Reasoning Tree with Validation), a training-free framework combining adaptive tree exploration, tool-augmented refinement, typed-failure backtracking, dual-critique scoring, and persistent self-rewriting memory. On the full MATH-500 benchmark, ReTreVal achieves 85.8% pass@1 with ground-truth-assisted verification and 84.2% (421/500) without reference answers in the inference loop. Under label-free verification on MMLU-Pro, it reaches 54.4% (544/1000), compared with 39.1% for Self-Refine. On full-scale label-free MATH-500, cross-problem Reflexion and Self-Refine with persistent memory reach 81.0% and 83.2%, respectively. Across three full-scale reshuffles, MATH-500 varies from 84.8% to 86.2% (1.4 points) and MMLU-Pro from 53.6% to 54.9% (1.3 points), providing no evidence of a large sequence effect in the tested runs. These results position ReTreVal as an auditable structured-inference procedure that performs targeted recovery and retains bounded failure experience without modifying model weights.

Primary area:
foundation or frontier models, including LLMs
Keywords:
large language models, reasoning, tree search, test-time / inference-time scaling, self-refinement, cross-problem memory, backtracking, tool-augmented reasoning, in-context learning, LLM agents

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_ERj8OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

In this paper, the authors propose ReTreVal, a training-free inference-time framework that allows an LLM to accumulate typed failure experience across a problem sequence without updating model weights. It couples complexity-adaptive tree exploration, per-node tool-augmented refinement, dual-critique scoring with historical approach-skepticism penalties, typed-failure backtracking to unexplored root-level siblings, and a persistent self-rewriting memory. Across MATH-500 (using Qwen 2.5 32B Instruct) and 1,000 MMLU-Pro problems (using Gemini 2.5 Flash), ReTreVal reaches 85.8% (ground-truth-assisted) and 84.2% (label-free) accuracy on MATH-500, and 54.4% (label-free) on MMLU-Pro, outperforming single-path, tree-search, and self-consistency baselines.

Critical strengths

First, when validation rejects an initial candidate solution, ReTreVal introduces a typed-failure backtracking strategy to avoid repeating the same flawed path with generic feedback, and instead switches to the highest-scoring unexplored root-level sibling node. Before refining that sibling, the proposed method diagnoses the failed attempt along two explicit dimensions: root cause and approach type. It further injects this structured failure record directly into the sibling's critique history so the same error class cannot recur.

Furthermore, a primary barrier to deploying test-time cross-problem memory is unbounded context growth, noise accumulation, and sensitivity to problem ordering. The paper provides concrete empirical evidence that its consolidation rules solve the context-bloat problem while still delivering substantial accuracy gains: across the full 500-problem label-free MATH-500 run, the memory store stabilized at just four entries and injected at most three entries, averaging 66 tokens per prompt, ensuring per-prompt memory overhead never scales with the number of problems.

Critical weaknesses

Table 2 gives the label-free comparison on MATH-500 with memory-equipped baselines. ReTreVal scores 84.2% and Self-Refine with a persistent memory buffer scores 83.2%. This gap is marginal, if we consider the run-to-run performance variation shown in the order study of Section 6.6. This is an important test to support the main claim of the paper, 'LLMs can improve on their own in the inference time'. However, the marginally small gain of ReTreVal seems undermining the claim. In contrast, the gap between ReTreVal is larger on MMLU data, as reported in Table 4. Is there any interpretation to the varying magnitude of the performance gap across two different datasets ?

Questions for authors

1/ What are the exact average input/output token counts, total LLM calls per problem, and wall-clock latency for ReTreVal compared to each baseline in Tables 1–4?

2/ Please elaborate on why, on MATH-500, the performance gap between ReTreVal and Self-Refine is marginal, and yet on MMLU, this gap becomes significantly larger. Does the gap variation originate from any difference between the characteristics of the two datasets?

Reviewer_sQomOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes ReTreVal, a training-free reasoning framework combining adaptive tree search, tool-assisted refinement, dual-critique scoring, typed-failure backtracking, and persistent self-rewriting memory. Its central contribution is a mechanism for accumulating failure information across problems and using it to guide subsequent reasoning without updating model parameters.

The authors evaluate ReTreVal on MATH-500 and MMLU-Pro, reporting 84.2% and 54.4% accuracy under label-free verification, respectively. They additionally conduct ablations, compare against existing reasoning frameworks, and investigate sensitivity to problem ordering.

Critical strengths
  • S1: The paper presents a reasonably comprehensive inference-time framework that combines multiple reasoning strategies, tool-based verification, failure classification, and cross-problem memory. The integration is practically relevant for repeated problem-solving settings where model weights cannot be updated.
  • S2: One of the important positive result is that ReTreVal retains much of its reported MATH-500 performance when ground-truth answers are removed from the inference loop (84.2% versus 85.8%). This addresses a meaningful practical limitation of reasoning frameworks that depend on knowing whether a proposed answer is correct before deciding to retry. It provides some evidence that the overall approach can operate without privileged correctness feedback.
Critical weaknesses
  • W1: The paper claims to be the first to demonstrate inference-time cross-problem learning through persistent failure memory. However, Dynamic Cheatsheet already investigates a closely related setting, maintaining and revising reusable strategies across reasoning problems without parameter updates. ReasoningBank and ExpeL also explore extracting transferable insights from previous experiences. The paper does not adequately differentiate its contribution from these approaches. Furthermore, ReTreVal achieves 84.2% on label-free MATH-500 compared with 83.2% for Self-Refine with a persistent memory buffer, a difference of only five problems. The experiments do not isolate the benefit of self-rewriting over simpler memory mechanisms, report how frequently memory entries are rewritten, or directly demonstrate improvement as cross-problem experience accumulates. Consequently, the novelty and empirical contribution of the proposed memory mechanism remain insufficiently established.

  • W2: Several reported results cannot be reconciled:

    • Table 1 reports 429 correct answers for ReTreVal versus 386 for Zero-Shot CoT, a net difference of 43, while Section 6.7 reports 37 wins and 11 regressions, implying a net difference of 26. This also does not match the reported label-free difference of 35, assuming the same Zero-Shot CoT baseline.
    • Table 5 reports 101 correct answers on decomposed MATH-500 problems and 295 on non-decomposed problems, totaling 396/500, inconsistent with both the reported 429/500 ground-truth-assisted and 421/500 label-free results.
    • Table 5 reports 70.7% Zero-Shot CoT accuracy on MATH-500 Levels 4–5, whereas the level-wise results in Table 1 imply approximately 66.8%.

    More importantly, Table 5 labels its ablations as label-free while using the 85.8% MATH-500 result from ground-truth-assisted verification. Under that protocol, reference-answer correctness determines when backtracking is triggered. Thus, the reported +9.0 percentage-point contribution of backtracking on MATH-500 reflects oracle-assisted error detection rather than demonstrated label-free recovery. These inconsistencies and protocol differences materially weaken confidence in the reported component-level improvements.

Questions for authors
  • How does the proposed self-rewriting memory differ from existing cross-problem learning approaches, particularly Dynamic Cheatsheet and ReasoningBank, as well as experience-based adaptation methods such as ExpeL and GEPA? Can the authors provide direct evidence that self-rewriting improves over simpler persistent memory mechanisms and demonstrate how performance changes as cross-problem experience accumulates?
  • Can the authors reconcile the win/regression counts in Section 6.7 with Table 1, and the decomposition totals in Table 5 with the reported overall accuracies? Were these results obtained from different runs or verification protocols?
Reviewer_qgzCOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
1
Read review
Paper summary

Paper proposes a training-free inference-time framework combining LLM-rated complexity, three failure signals, per-node tool augmention refinement, node scoring, typed failure backtracking with one retry, and "self-rewriting" memory

Main results: MATH-500 on Qwen2.5-32B-Instruct: 85.8% vs. 81.0% for cross-problem reflexion + 83.2% for refine & memory. MMLU-Pro: 54.4% vs. 39.1% for Self-Refine. Attribution: +9% backtracking, +8.6% memory, +5.6% tools.

Critical strengths

Did not find a strength that met the bar.

Critical weaknesses

TL;dr: novelty claims incorrect, related work missing.

Test time experience accumulation is an established line of work, and many training-free experience/memory agents exist (simple Google Search). The burden is on the authors to identify and differentiate their work from existing approaches & they have not done this in this paper submission.

For the MATH 500 win, this should not be compared with single-pass baselines. The mixture of too many changes in one ablation make it very hard to tease what actually helped.

In MMLU Pro Zero-Shot CoT with Gemini 2.5 Flash scores 19.2% and ReAct 17.4%, barely above the 10% chance level, whereas Gemini 2.5 Flash is publicly reported far higher on MMLU-Pro.

The compute comparison is done with k samples, but each "ReTreVal" attempt involves tree expansion over up to 4 children of depth 5. Comparing ReTreVal pass@5 over its own attempts with independent-sample pass@8 is also not apples-to-apples.

ReTreVal (429) minus ZS-CoT (386) is a net 43 problems, but the error analysis reports 37 wins and 11 regressions, a net 26.

All results are single runs with no CIs; reported margins are mostly 5–9 problems.

Questions for authors

Why do the two benchmarks use different backbones? How can ZS-CoT score 68.0% on the decomposed subset but ~7% on the rest Report all MATH-500 results and with baselines for apples to apples. Compare cross-problem memory methods Reconcile the win/regression counts with the 43-problem net difference

Reviewer_718TOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper introduces ReTreVal, a training-free reasoning framework combing adaptive tree search, tool-augmented refinement, typed-failure backtracking, critique-based scoring, and persistent self-rewriting memory. The memory retains experience across problems without updating the model weights. Experiments cover MATH-500 and 1,000 MMLU-Pro questions with both ground-truth-assisted and label-free verification settings.

Critical strengths

Retaining and revising failure experiences across problems is a useful direction. The authors include a full label-free MATH-500 evaluation and comparisons with persistent-memory versions of existing methods, rather than relying entirely on reference-answer feedback. These are relevant controls for accessing the proposed cross-problem memory.

Critical weaknesses
  • The "compute-matched" comparison does not actually match compute. Tab3 compares independent samples with ReTreVal attempts, but Sec6.3 explicitly states that each ReTreVal attemp includes tree expansion, critique, and tool calls and is more expensive than one sample. Comparing 4.2 attempts against 5 or 8 samples then does not give an advantage at comparable cost in the first place. I don't think the conclusion that the gains are not explained by additional sampling is supported by experiments if there is no measured token usage, model calls, or runtime.

  • Several reported results do not reconcile. In tab5, the decomposed and non-decomposed MATH groups certain 101 and 295 correct answers. These groups over 500 problem I believe but the the toal sum is 396? not the reported full system total as 429 or the label free total of 431. Similar patterns persist throughout the manuscript (e.g., sect6.7 vs. tab1 conflicts). I would suggest a careful proofreading of this current submission.

  • The claimed benefits of self-writing and typed failures are not sufficiently isolated. The memory ablation removes cross-problem memory all together, instead of retaining memory while disabling rewriting. Similarly, removing backtracking does not distinguish typed failure feedback from an ordinary retry with generic feedback. In label free comparison ReTreVal exceeds memory augmented self-refine by only five problems without a corresponding matched-cost comparison. So the claim that typed records structurally prevent an error class from recurring is also too strong and not fully validated: the described mechanism adds labels and explanations to the next prompt, rather than enforcing a constraint that excludes those errors.

Questions for authors

See weakness and more concretely:

Q1: Can you explain the subgroup deficits in tab5 and the win/regression counts in sec6.7 with the main results? please identify the run and verification protocols behind each analysis and provide the corresponding per-problem outcomes.

Q2: Does ReTreVal retains its advantage under matched total inference budgets, including expansion, critique, refinement, and memory-update calls?

Q3: Within the same research framework and budget, what is the benefit of rewriting memory entries rather than retaining them without rewriting, and of typed failure feedback rather than generic feedback? Does typed feedback measurably reduce recurrence of the same error class?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.