TreeHCA: Hindsight-Guided Exploration and Credit Assignment for Multi-Turn LLM Agents

• GRPO assigns every generated token the same trajectory advantage, so successful rollouts can reinforce unhelpful turns and failed rollouts can penalize useful decisions.Source: §1 · p. 1
• HCA can refine intermediate credit, but policy-generated chains may lack informative alternatives at consequential histories.Source: §1 · pp. 1–2
• TreeHCA revisits histories after turns that reduce success likelihood, sampling alternatives from their parent while retaining the original path for shared-prefix comparisons.Source: §1 · p. 2
• Because hindsight-selected continuations change the sampling distribution, TreeHCA uses inverse hindsight weights to correct credit estimates for the original rollout policy.Source: §1 · p. 2
• Across seven question-answering benchmarks and three Qwen backbones, TREEHCA outperforms all compared methods in aggregate exact match; its paired design also achieves the strongest EM and F1 in the component study.Source: §1 · p. 2

• GiGPO forms groups around comparable states, HCAPO uses outcome-conditioned LLM scores, and IGPO uses reference-answer likelihood changes as information-gain rewards (Feng et al., 2025; Tan et al., 2026; Wang et al., 2026).Source: §2 · p. 2
• Tree-GRPO, AEPO, AT2PO, and IGRPO combine tree sampling or adaptive exploration with turn-level learning, while TreeHCA studies hindsight-selection sampling and its matching inverse weighting (Ji et al., 2026; Ding & Ye, 2026; Zhang et al., 2026).Source: §2 · p. 3

• An agent’s trajectory consists of completed reasoning-and-action turns with observations, ending in a final-answer action and a binary verifier reward.Source: §3 · p. 3
• During each rollout-collection round, the behavior policy is held fixed, and its continuation probabilities define history values and decision values.Source: §3 · p. 3
• Shared-prefix trajectories form a tree whose sibling turns provide alternatives and whose leaves carry verifier outcomes; the reference answer scores alternatives during training.Source: §3 · p. 3

4.1 SAMPLING VIA CREDIT ASSIGNMENT

• A negative hindsight log ratio identifies a decision after which success is less likely than at its parent, while the exact ratio ranks candidate decisions by expected terminal reward.Source: §4.1 · pp. 3–4

4.2 SCORING HISTORIES WITH THE POLICY LLM

• The policy teacher-forces the reference answer after a fixed answer-eliciting instruction and uses mean token log probability to score history compatibility.Source: §4.2 · p. 4
• A completed turn’s score is the change in reference-answer compatibility from before to after the turn, including the information supplied by its tool observation.Source: §4.2 · p. 4

4.3 SELECTING AND COMPLETING ALTERNATIVES

• At selected parent histories, TreeHCA scores N candidate decisions, continues one sampled by normalized hindsight scores, and retains the original child and subtree for learning.Source: §4.3 · pp. 4–5, Figure 2 · p. 4

5.1 THE SAMPLING AND ESTIMATION CORRESPONDENCE

• Hindsight-guided selection favors high-scoring continuations, so inverse-score weighting corrects policy-based expectations, with an exact correction for every finite pool size.The finite-pool identity accounts for the sampled candidates rather than relying only on the direct-tilt approximation.Source: §5.1 · p. 6

5.2 FROM LEAF REWARDS TO TURN-LEVEL ADVANTAGES

• Leaf verifier rewards are group-normalized per prompt, with zero variance yielding zero learning signal; reverse-order backup inherits single-child signals and normalizes branch signals into a convex combination.The tree operator applies this normalized backup to retained children using inverse scores.Source: §5.2 · p. 6

5.3 TURN-LEVEL POLICY OPTIMIZATION

• Policy tokens receive the advantage of their completed turn, while tool outputs and prompt tokens remain in the history but are masked from the loss.A shared-prefix turn receives the same node advantage in every descendant trajectory.Source: §5.3 · pp. 6–7
• The GSPO-token policy-update ratio compares updated and behavior policies; unlike inverse-hindsight weights, it does not correct continuation selection.Advantages are held fixed during the update.Source: §5.3 · pp. 6–7

6.1 SETUP AND COMPARISON PROTOCOLS

• The experiments compare chain and tree baselines across seven QA benchmarks, using Qwen2.5-3B-Instruct, Qwen3-4B, and Qwen3-8B; Qwen3 tree methods share an expansion budget.Aggregate scores weight datasets by test-set size; the component comparison examines exploration and credit rules in turn.Source: §6.1 · p. 7, §6 · p. 7

6.2 HINDSIGHT-GUIDED EXPLORATION

• 44.9 aggregate EM gives TREEHCA the highest score in the Qwen2.5 tree-based comparison, 0.6 percentage points above HCAPO.The table compares tree-based baselines on EM (%).Source: Table 2 · p. 8, §6.2 · p. 8
• At 8B, TREEHCA exceeds AEPO by 1.63 points on multi-hop QA and 0.81 points on single-hop QA, leading all seven methods on both task families.It also has the highest weighted EM at both Qwen3 model sizes and task families.Source: Table 3 · p. 8, §6.2 · p. 8

6.3 CREDIT ASSIGNMENT AND THE PAIRED CONSTRUCTION

• 51.76 EM is highest with hindsight exploration and TREEHCA credit; under AT2PO credit, entropy beats hindsight, 50.78 to 49.60 EM.The component comparison varies exploration and credit rules on Qwen3-4B HotpotQA; the effect of changing exploration depends on the credit rule.Source: §6.3 · pp. 8–9, Table 4 · p. 9

6.4 VARIABILITY AND TRAINING COST

• Across three seeds, weighted EM is 48.52 ± 0.75 for Qwen3-4B and 50.25 ± 1.27 for Qwen3-8B; larger deviations on some benchmarks indicate greater seed sensitivity.The reported aggregate gains over the strongest baseline are 0.90 and 1.63 points, respectively, and exceed one standard deviation of TREEHCA's observed run variation.Source: Table 5 · p. 9, §6.4 · p. 9
• Training takes 34.40 versus 31.50 hours at 4B and 36.20 versus 32.58 hours at 8B for TREEHCA and AT2PO, respectively.These are increases of 9.2% and 11.1% under the shared expansion budget.Source: §6.4 · p. 9

7 CONCLUSION

• TREEHCA uses a common hindsight change of measure to connect exploration with intermediate credit.Hindsight scores select alternative continuations, while inverse weights account for that sampling preference when estimating advantages.Source: §7 · p. 9
• The method derives corrections for hindsight-tilted proposals and finite-pool candidate selection, then uses a normalized tree backup.Component experiments connect performance to combining exploration and credit.Source: §7 · p. 9
• Across the evaluated question-answering settings, the paired construction improves on the compared baselines.The paper identifies the pairing as the central design principle behind these gains.Source: §7 · p. 9

REPRODUCIBILITY STATEMENT

• TreeHCA’s code is available at github.com/TheBlackCat22/TreeHCA.The paper directs readers to Sections 4 and 5 for the exploration rule and learning objective, with proofs and estimator conditions in Appendix D.Source: REPRODUCIBILITY STATEMENT · p. 10

A DETAILED RELATED WORK

• The related-work overview organizes methods by how they collect alternatives and turn outcomes into learning signals.It frames intermediate credit as depending on both information at a decision and the continuations used to assess it.Source: A DETAILED RELATED WORK · p. 12

A.1 HINDSIGHT DISTRIBUTIONS AND PRACTICAL ACTION CREDIT

• Hindsight credit assignment relates outcome-conditioned action probabilities to action values, while GiGPO and HCAPO derive practical intermediate signals from collected trajectories.TreeHCA instead uses reference-answer scores to direct the collection of alternatives.Source: §A.1 · p. 12

A.2 OUTCOME AND PROCESS FEEDBACK ALONG POLICY TRAJECTORIES

• Process-feedback methods refine credit within collected chains, whereas TreeHCA also uses answer information to allocate additional rollout budget.Examples include StepSearch’s evidence-coverage and repetition rewards and IGPO’s changes in reference-answer likelihood.Source: §A.2 · p. 12

A.3 TREE STRUCTURE, EXPLORATION CRITERIA, AND CREDIT AGGREGATION

• Tree-based methods reuse shared prefixes or propagate terminal signals, while entropy-guided methods allocate exploration using uncertainty-related criteria.TreeHCA connects history and candidate selection to reference-answer compatibility and the corresponding sampling correction.Source: §A.3 · pp. 12–13

A.4 THE SAMPLING DISTRIBUTION AND POLICY OPTIMIZATION

• IGRPO allocates rollout expansion from answer likelihood and parent improvement, while TreeHCA targets the original rollout-policy expectation at selected parents.For TreeHCA, this target connects continuation selection to reciprocal weighting.Source: §A.4 · p. 13
• For finite candidate pools, the exact correction recovers the base-policy expectation; the practical tree backup normalizes inverse proxy scores over retained siblings.The backup follows tree credit assignment before policy optimization acts on turn-level advantages.Source: §A.4 · p. 13

B.1 HYPERPARAMETERS

• The rollout tree starts with M complete trajectories and adds alternatives from up to K selected parents in each of L expansion rounds.The appendix also lists score smoothing, a negative exploration threshold, a sibling penalty, and candidate count N as exploration controls.Source: §B.1 · p. 13

B.2 RUNTIME

• Qwen3 experiments ran on an eight-NVIDIA-H200-GPU cluster, and wall-clock training times are reported for Qwen3-4B and Qwen3-8B under AT2PO and TreeHCA.Other reported settings include optimizer, learning rate, clipping, batch sizes, prompt and response lengths, and tool-call limits.Source: §B.2 · p. 13, §B.1 · p. 13

B.3 CODE DETAILS

• The Qwen3 experiments build on AT2PO code and VeRL, while Qwen2.5-3B experiments add TreeHCA to the IGRPO codebase built on VeRL-agent.Source: §B.3 · pp. 13–14

C ADDITIONAL COMPONENT MEASUREMENTS

• 65.88 F1 is reported for the complete hindsight-guided exploration and credit pair in the Qwen3-4B HotpotQA component comparison.Table 4 reports EM and F1 for six rows; all use seed 42, and the accompanying validation scores are a separate measurement.Source: Figure 3 · p. 15, C ADDITIONAL COMPONENT MEASUREMENTS · p. 15

D.1 THE RETURN-CONDITIONED HCA IDENTITY

• The return-conditioned identity treats complete interaction histories as states, composite turns as actions, tool observations as transitions, and terminal verifier reward as return.For binary rewards, the success-conditioned ratio ranks actions at a common parent when its value is positive.Source: §D.1 · p. 15

D.2 EXACT IMPORTANCE IDENTITIES

• The finite-pool correction is exact conditional on the candidate pool, and its correction uses the mean score across all proposed candidates, including uncompleted ones.Averaging over iid candidates recovers the base-policy expectation; support coverage is required for nonzero target contributions.Source: §D.2 · p. 16

D.3 THE MARGINAL LAW OF FINITE-POOL SELECTION

• The marginal law of finite-pool selection approaches the normalized score tilt as pool size grows, under bounded scores bounded away from zero.The practical normalized sibling backup instead uses completed children retained in an adaptively constructed tree, so its scores and downstream signals are coupled to tree construction.Source: §D.3 · p. 16

D.4 SELF-NORMALIZED ESTIMATION AND TREE BACKUPS

• Under iid direct-tilt sampling and the stated support and integrability conditions, the self-normalized estimator converges almost surely to the base-policy expectation.At finite sample size, the ratio of random sums generally introduces bias.Source: §D.4 · p. 17
• Positive backup scores yield nonnegative weights summing to one, keeping a parent signal between its smallest and largest child signals.A single-child node passes its child’s signal unchanged, and equal leaf rewards propagate a zero signal.Source: §D.4 · p. 17
• The change-of-measure propositions address a fixed integrand and specified selection law, while the evaluated algorithm combines proxy scores, an adaptive finite tree, group-relative leaf normalization, and clipped GSPO.Source: §D.4 · p. 17

E TREE-CONSTRUCTION IMPLEMENTATION DETAILS

• Each exploration step executes N candidate turns, scores completed turns, then continues only the selected candidate to termination.Clipping assigns the threshold score to unflagged nodes; selection expands flagged nodes in score order and fills remaining slots uniformly at random.Source: E TREE-CONSTRUCTION IMPLEMENTATION… · p. 17
• For Qwen2.5-3B, TreeHCA branches during rollout when the hindsight ratio falls below a threshold, sampling two alternatives while keeping total rollout budget comparable to GRPO.Source: E TREE-CONSTRUCTION IMPLEMENTATION… · p. 17

F RESEARCH ASSETS

• Experiments use Qwen2.5 and Qwen3 models across seven QA benchmarks, with reference answers used for training-time hindsight scoring and evaluation.Retrieved passages enter the history as tool observations and are masked from policy-token loss.Source: F RESEARCH ASSETS · p. 17

G SAMPLE GENERATIONS DURING TRAINING

• The shared-prefix rollouts contrast an immediate wrong answer (R = 0) with a successful follow-up search (R = 1).The successful continuation reformulates the query to retrieve the Miami Heat’s 2012 opponent, Oklahoma City Thunder.Source: G SAMPLE GENERATIONS DURING TRAINING · pp. 17–18, Table 11 · p. 19, Table 12 · p. 20
• The alternatives share retrieved passages mentioning several NBA Finals series, but the successful branch retrieves an explicit statement of the required fact.The unsuccessful branch answers immediately from ambiguous passages, while the successful branch reformulates its query.Source: G SAMPLE GENERATIONS DURING TRAINING · pp. 17–18, Table 10 · p. 19, Table 11 · p. 19
• A hindsight ratio below κbr triggers candidate-decision sampling and selection from a hindsight-guided distribution during chain construction.The selected decision is appended with its observation, and construction stops if it produces a final answer.Source: G SAMPLE GENERATIONS DURING TRAINING · p. 18