acceptodds
Under review as a conference paper at ICLR 2027

TREEHCA: Hindsight-Guided Exploration And Credit Assignment For Multi-Turn LLM Agents

Abstract

Outcome-supervised group-relative policy optimization (GRPO) gives every token in an LLM agent's trajectory the same advantage, leaving useful and unhelpful decisions undifferentiated. Hindsight credit assignment (HCA) can refine this feedback, but its estimates depend on trajectories containing informative alternatives at consequential histories. We introduce TreeHCA, which couples sampling via hindsight ratios to generate these alternatives with hindsight credit assignment to evaluate their contribution. We use changes in reference-answer likelihood to revisit intermediate histories and select alternative continuations, forming a tree of reasoning and tool interactions. This exploration changes the distribution of sampled continuations. We derive the corresponding inverse-hindsight importance correction, including an exact finite-pool identity, and use its structure in a normalized tree backup that propagates terminal outcomes into turn-level advantages. This common hindsight structure is TreeHCA's central design principle, linking informative exploration to hindsight-guided credit assignment. Across seven question-answering benchmarks and three Qwen backbones, TreeHCA outperforms every baseline in aggregate exact match, validating our paired design for multi-turn LLM training.

Primary area:
reinforcement learning
Keywords:
LLM agents, reinforcement learning

Reviews

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

This paper proposes TreeHCA, a framework that jointly addresses exploration and credit assignment in multi-turn LLM agents trained with terminal rewards. The method uses changes in reference-answer likelihood to identify consequential intermediate decisions and guide the sampling of alternative continuations. It then applies inverse-hindsight weighting in a tree-based backup to propagate terminal rewards into turn-level advantages. The authors derive importance-weighting identities to motivate the connection between hindsight-guided sampling and credit estimation. Experiments across seven question-answering benchmarks and three Qwen backbones demonstrate improvements in aggregate exact match over existing chain-based and tree-based methods, while component ablations support the benefits of combining hindsight-guided exploration with credit assignment.

Critical strengths
  1. TreeHCA connects hindsight-guided exploration with inverse-weighted credit assignment through a shared change-of-measure perspective. The finite-pool importance-weighting identity provides a principled motivation for linking sampling decisions to turn-level credit, representing a valuable methodological contribution.
  2. The paper demonstrates improvements in aggregate exact match across seven QA benchmarks and three Qwen backbones. The component ablation further shows that combining hindsight-guided exploration with the proposed credit assignment achieves better EM and F1 than alternative combinations, supporting the effectiveness of the paired design.
Critical weaknesses
  1. Proposition 1 establishes an exact importance correction under specific sampling assumptions, but the practical tree backup uses self-normalized inverse scores over adaptively selected children. The theoretical guarantees do not directly extend to this estimator, weakening the claimed principled connection between exploration and credit assignment.
  2. The proposed method uses changes in reference-answer likelihood as a proxy for the conditional probability of terminal success. However, the paper provides limited evidence that these scores reliably identify consequential decisions or accurately reflect their contributions to successful outcomes. This uncertainty affects the validity of both the exploration strategy and the resulting credit assignment.
Questions for authors
  1. Proposition 1 establishes an exact importance correction for finite-pool sampling, whereas Eq. (14) applies self-normalized inverse weights to adaptively retained tree children. Could the authors clarify which theoretical properties extend to the practical estimator and how the differences between these sampling settings affect the validity of credit assignment?
  2. The practical method uses changes in reference-answer likelihood as a proxy for conditional terminal success probabilities. What evidence supports the reliability of this approximation in identifying consequential decisions? Are there existing analyses showing that lower hindsight scores correspond to reduced success probabilities or that alternative continuations improve outcomes?
Reviewer_HUN5OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The authors propose an improved training methodology for multi-turn LLM agents by using the known reference answer to identify which intermediate decisions likely helped or hurt the final outcome. It then branches from poorly-scoring decisions to explore alternative continuations and uses inverse weighting to turn the resulting tree of successes and failures into turn-level training signals. The core claim is that exploration and credit assignment should be designed together, and that the same hindsight signal that decides where to explore should also determine how those selectively-sampled trajectories are weighted during learning.

Critical strengths

The core idea is solid: intermediate decisions in a long agent rollout should not all receive the same credit, we should disentangle which steps helped and which ones hurt. TreeHCA proposes a principled way to target exploration at consequential decisions and to correct for that biased sampling when assigning credit.

I also like how exploration and learning rules are tightly coupled instead of being stapled together in some ad-hoc way. The same hindsight signal guides both where the tree branches and how outcomes are propagated back. That paired design is tested empirically against chain-based and tree-based baselines across several tasks and model sizes.

Critical weaknesses

TreeHCA’s central claim is that one hindsight score both steers exploration and, through its inverse, corrects for that steering when assigning credit. But the actual algorithm they use is different. Proposition 1 shows that inverse-score weighting recovers the policy’s expected outcome for samples chosen by score-weighted selection, and its exact version weights by the mean score of all N candidates. The tree backup in Eq. 14 instead applies inverse-score weights to the siblings kept in the tree. At a revisited parent, these include the original child, which the policy sampled and which was not chosen by score-weighted selection, so the correction doesn’t apply to it. The backup also ignores the scores of the candidates that were discarded. The paper acknowledges in Appendix D.3 that the kept siblings are coupled to how the tree was built, and in D.4 it says the propositions only motivate the algorithm.

The correction also only adjusts the advantage given to parent turns. The training loss averages equally over every root-to-leaf trajectory, so the alternatives added by score-weighted selection enter the gradient with no correction. The GSPO ratio only compares the updated and behavior policies.

The direct test of the pairing is a single-seed ablation on HotpotQA validation, where the full method beats entropy exploration with the same credit rule by 0.59 EM. For the same model, the paper reports a seed-to-seed standard deviation of 2.30 EM on HotpotQA in its main evaluation. With AT2PO’s credit rule, hindsight exploration does worse than entropy, 49.60 versus 50.78.

The headline gains are small: 0.90 and 1.63 EM on multi-hop and 0.83 and 0.81 on single-hop over the strongest baseline. Variance is reported only for TreeHCA, and several baselines are copied from another paper rather than rerun. In the Qwen2.5 experiments, Algorithm 2 as written replaces the original decision with the selected one and produces a single trajectory. That leaves no siblings for the backup to weight, so those results don’t test the pairing.

Questions for authors

The theory and the algorithm need to be about the same thing. One option is to make the estimator match the theory: store the scores of all N candidates and weight the selected alternative by the exact finite-pool weight (mean candidate score divided by its own score). Then give the original child its plain policy weight, or leave it out of the parent’s estimate, since its revisit was triggered by its own score. The other option is to keep the current backup and measure its bias directly. For a sample of histories, estimate the true value with many plain policy rollouts, then compare the backup’s estimate against a uniform average and the exact finite-pool weight.

The second problem to fix is that the correction never reaches the gradient. The authors should multiply the loss for tokens from a selected alternative and its descendants by the same exact weight, clipped or self-normalized if variance is a problem. They should then compare training with and without this weighting. Otherwise they should admit that the method trains on the score-tilted distribution, as IGRPO does, and drop the claim that it targets the rollout policy’s expected outcome.

Ablation behind the main claim weak. The authors should rerun Table 4 with at least three seeds, report it on the test split, and cover both Qwen3 sizes and both task families. They should add the two rows that isolate the pairing: hindsight exploration with an unweighted backup, and hindsight exploration with the exact finite-pool weight. Paired significance tests across questions would show whether differences of half a point are real.

Finally, there's the comparison itself. The authors should rerun GRPO, GSPO and AEPO under their own protocol instead of copying them from Zong et al., and do the same for Tree-GRPO instead of using Zhang et al.’s reproduction. They should run AT2PO, TreeGRPO and every other baseline with the same seeds as TreeHCA and report variance for all of them. This matters because the Qwen3 margins are under two points, and the Qwen2.5 margin over HCAPO is 0.6 EM. For Qwen2.5, they should either run the tree version from Algorithm 1, or relabel Algorithm 2 as hindsight-guided resampling and stop presenting those results as evidence for the pairing. They should also recheck HCAPO’s Bamboogle score of 64.5 in Table 1, since the other methods there score between 11.1 and 32.4.

Reviewer_QrvJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper argues that outcome-supervised GRPO gives the same advantage to every turn of a multi-turn agent trajectory, so useful and harmful decisions are not separated. It proposes TreeHCA, which links exploration and credit assignment through one "hindsight score".

(1) Hindsight-guided exploration. The score delta(c) is the change in the policy's teacher-forced log-likelihood of the reference answer before and after a turn. Turns with delta below a negative threshold are selected. From each selected turn's parent, N candidate turns are sampled from the policy and executed. One of them is chosen with probability proportional to exp(delta) and continued to the end, while the original subtree is kept.

(2) Hindsight-guided credit assignment. Group-normalized leaf rewards are backed up through the tree. At each node, the children are weighted by their inverse scores (1/rho_hat), normalized over the children kept in the tree. The goal is to undo the exploration's preference for high-scoring children.

The theory gives an importance-sampling identity for the score-tilted proposal, an exact finite-pool identity, and the marginal law of finite-pool selection. Turn-level advantages are optimized with GSPO-token.

Experiments use seven search-based QA benchmarks with Qwen2.5-3B-Instruct (against chain and tree baselines) and with Qwen3-4B and Qwen3-8B (against GRPO, GSPO, TreeGRPO, AEPO and AT2PO). TreeHCA reports the highest aggregate EM in every setting, with three seeds for Qwen3, a single-seed component study on HotpotQA, and about 9-11% more training time than AT2PO.

Critical strengths
  1. A natural and clearly explained idea. If exploration selects continuations in a biased way, the credit computed from them should correct for that bias. Figures 1 and 2 explain this link clearly, and the appendix is honest that the practical backup is not exactly the estimator covered by the theory (Appendices D.3 and D.4). This idea is a useful contribution to tree-based RL for LLM agents.

  2. Consistent results on the Qwen3 backbones. In Table 3, TreeHCA has the highest weighted EM for both model sizes and both task families, against six baselines, and Table 5 reports three seeds. The weighted averages in Table 3 are consistent with the per-dataset numbers. The extra training cost (about 9-11% over AT2PO) is reported clearly.

Critical weaknesses
  1. The central claim, that the paired exploration and credit design is what produces the gains, is not well supported.
  • The component study (Table 4) uses a single seed. The key differences are small: hindsight versus entropy exploration with TreeHCA credit is 51.76 versus 51.17 EM, a gap of 0.59. Table 5 reports a standard deviation of 2.30 on HotpotQA for the same backbone, so most of the differences in Table 4 are within seed noise.
  • The inverse weighting, which is the core of the second contribution, is never tested alone. Table 4 compares TreeHCA credit only with AT2PO's entropy-weighted backup. There is no row with hindsight exploration plus a uniform (mean) backup, or plus a non-inverse rho_hat-weighted backup.
  • With AT2PO credit, hindsight exploration (49.60) is worse than entropy exploration (50.78). This interaction is interpreted as support for "pairing", but one seed cannot support that reading.
  • The theory does not match the implementation: (a) The abstract highlights an exact finite-pool identity (Eq. 11), but the backup (Eq. 14) does not use the finite-pool weight (mean score divided by selected score). It normalizes 1/rho_hat over the children kept in the tree. (b) Those children include the original child, which was sampled from pi and selected for expansion because its score was low. Giving it an inverse-score weight has no importance-sampling meaning. (c) The inverse weights change only the parent's advantage. The tokens of the tilt-selected continuation are trained as on-policy samples in GSPO, so the policy gradient is not corrected for the tilted sampling.
  • There is no evidence that delta (reference-answer likelihood change) tracks the true success probability Q/V. The link to the exact HCA ratio (Lemma 1) is therefore mostly naming.
  1. The Qwen2.5-3B comparisons (Tables 1 and 2) are not reliable as presented.
  • According to Appendix E, these results use a "rollout-matched variant", i.e. Algorithm 2 ("Hindsight-guided chain construction"). This variant keeps only the selected candidate and has no siblings, so the inverse-weighted backup is not used. Yet the tables label it "Tree-based".
  • The "Avg." values of the baselines do not match their own per-dataset numbers. With the standard test-set sizes, which reproduce TreeHCA's 44.9 exactly, the weighted averages are: Search-R1 37.7 (reported 37.4) ZeroSearch 39.5 (39.1) GiGPO 43.7 (43.3) IGPO 44.3 (43.6) HCAPO 44.1 (44.3) Tree-GRPO 41.2 (40.8) IGRPO 44.4 (43.9) With consistent averaging, the closest competitor is IGRPO, and the margin is only about 0.5 points, without seeds.
  • HCAPO's Bamboogle score of 64.5 is far outside the range of all other methods (11 to 32) and is likely a typo.
  • Baseline numbers come from different papers with different settings: ZeroSearch uses simulated search, and the Tree-GRPO numbers are taken from another paper's reproduction. TreeHCA is trained for 200 steps with 512 rollout tokens, so the comparison is not controlled.

Novelty is also limited. IGRPO (Zhang et al., 2026) already uses reference-answer likelihood with exponential tilting to guide tree expansion, IGPO uses the same likelihood change as a turn reward, and AT2PO already combines tree search with a weighted backup. Proposition 1 is standard importance sampling, Eq. 11 is a one-line identity, and Lemma 1 restates Theorem 5 of Harutyunyan et al. (2019). If IGRPO counts as concurrent work under ICLR policy, this concern is smaller, but the relation should still be stated clearly in the main text.

Questions for authors

Clarifications (answers could change my assessment):

  1. Were the Qwen2.5-3B results in Tables 1 and 2 produced with Algorithm 2 (chain construction, no sibling backup)? If so, why are they labeled "Tree-based"?
  2. How were the baseline averages in Tables 1 and 2 computed? Please recompute all of them with the same weighting. Is HCAPO's Bamboogle score of 64.5 a typo?
  3. What are the results of hindsight exploration with (a) a uniform mean backup and (b) a rho_hat-weighted (non-inverse) backup? Can you report Table 4 over at least three seeds?
  4. Does delta correlate with the true success probability, for example a Monte Carlo estimate of Q/V from repeated rollouts?
  5. Why does the original child, which is not sampled from the tilted proposal, receive an inverse-score weight in Eq. 14? Is the policy gradient for the tokens of the tilt-selected continuation corrected in any way?
  6. What is the total budget (tokens, tool calls, completed rollouts) for TreeHCA and AT2PO? How does "Rollout n = 16" in Table 6 match M + KL = 10 + 62 = 22?
  7. Where are the score smoothing epsilon_smooth and the sibling penalty gamma (Table 8) used? They do not appear in any equation or in Algorithm 1.

Suggestions and minor issues (would not change my score alone):

  • Algorithm 2, line 5 compares rho_hat (a positive ratio) with kappa_br = -0.14. This condition can never be true; it should probably be log rho_hat = delta.
  • There are two different code links (anonymous.4open.science/r/TreeHCA and .../r/TreeHCA-83E6), and the abstract says "GitHub", but the link is not on GitHub.
  • Appendix C reports "validation scores" (51.56 ... 39.26) that differ from the EM in Table 4, which is also called validation. Please define this metric.
  • "6192 response tokens" (Section 6.1 and Table 6) looks like a typo.
  • In Table 5, Bamboogle at 4B is 53.60 +/- 0.00 over three seeds, i.e. exactly the same 67/125 in every run. Please confirm.
  • Notation is overloaded: s is used for the reasoning sequence, the score, the instruction and the GSPO ratio; N is used for candidates and token counts; "br" in kappa_br is not defined.
  • Figure 3 repeats the F1 column of Table 4, and its axis starts at 0, so the differences cannot be seen. The green shading plus bold plus underline in the tables is hard to read and is lost in grayscale.
  • The text is repetitive ("central design principle", "paired design", "central insight"). Several sentences add no information, e.g. in Appendix C and B.1. Shortening them would improve clarity.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.