Multi-turn agents stop scoring whole trajectories: revisiting weak turns and resampling lifts aggregate exact match on seven QA benchmarks
Lead
Multi-turn LLM agent training now ties exploration and credit assignment to one hindsight score: turns that lower the reference-answer likelihood are revisited and re-branched from the same parent, and inverse weights fold the outcomes back into the original policy, giving the highest aggregate exact match across seven QA benchmarks and three Qwen backbones.
Story
Intermediate decisions in a multi-turn agent are now scored by their contribution to final success instead of sharing one advantage value across the whole trajectory. Outcome-supervised group-relative policy optimization previously assigned the same trajectory advantage to every generated token, so a successful trajectory could reinforce unhelpful turns and a failed one could penalize useful decisions. On Qwen2.5-3B, TreeHCA reaches 44.9 aggregate exact match, above the chain-based HCAPO at 44.3 and the tree-based IGRPO at 43.9.
The method uses changes in reference-answer likelihood to find turns worth revisiting, then resamples alternative continuations from that turn's parent history, forming a shared-prefix tree of reasoning and tool interactions. Earlier intermediate-credit methods relied on policy-generated linear chains already containing informative alternatives, which are often sparse at consequential histories. On Qwen3-4B and Qwen3-8B, multi-hop weighted exact match rises from 47.62 to 48.52 and from 48.41 to 50.25 over AT2PO, and single-hop from 55.55 to 56.38 and from 56.75 to 58.75.
Exploration and credit assignment share one hindsight score: the score that guides sampling also sets the inverse weight needed to recover the original policy. Selecting by score makes high-scoring continuations more common, so their observed frequency alone cannot represent the rollout policy. In the component comparison, hindsight exploration with the TreeHCA credit rule reaches 51.76 exact match and 65.88 F1, versus 49.60 and 62.74 with AT2PO credit, and 51.17 and 64.17 for entropy exploration with TreeHCA credit.
What to watch
The reported scope is search-based question answering: seven benchmarks, the Qwen2.5-3B-Instruct, Qwen3-4B and Qwen3-8B backbones, with an agent alternating reasoning and queries to a Wikipedia index that returns the top three passages per query. Training uses reference answers to score candidates, while evaluation uses the ordinary policy and search tool. Qwen3 allows six tool calls and 6192 response tokens, with 250 training steps on HotpotQA for multi-hop and 200 on NQ for single-hop.
Across three training seeds, multi-hop standard deviations on individual benchmarks range from 0 to 2.30 points at 4B and from 0.36 to 4.53 points at 8B, and the authors note that some benchmarks are more sensitive to the training seed. The aggregate gains exceed one standard deviation of TreeHCA's observed run variation, but that statement covers only the reported seeds. Under AT2PO credit, entropy exploration outperforms hindsight, so the effect of changing the exploration rule depends on the credit rule. Self-normalization is a ratio of random sums at finite sample size and generally introduces bias.