acceptodds
Under review as a conference paper at ICLR 2027

GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents

17 views

Abstract

Group-based reinforcement learning (RL) has advanced large language models (LLMs) and is increasingly extending to agentic tasks, where sparse terminal rewards make step-level credit assignment essential. Existing methods assign credit from what follows an action in sampled rollouts, but do not explicitly capture its retrospective relation to the realized outcome. Hindsight credit assignment (HCA) instead attributes credit through the ratio of hindsight to behavior-policy probabilities, but estimating the hindsight distribution requires an auxiliary model or an extra pass. To address this estimation bottleneck, we propose GraphHCA, a model-free realization of HCA that eliminates explicit hindsight-distribution estimation. For terminal-goal tasks with deterministic transitions, Bayes' rule reduces the hindsight ratio to a ratio of behavior-policy success probabilities at consecutive states. Taking logs yields a state-wise success potential, whose increment across a transition provides step-level credit. GraphHCA estimates this potential from pooled rollouts through a discounted recursion on the induced transition graph, which admits a unique fixed point on any directed graph. The resulting step-level signal is combined with the trajectory-level advantage, requiring neither a learned hindsight model nor an extra forward pass and recovering GRPO when the step-level weight is zero. Among all compared baselines, GraphHCA achieves state-of-the-art results on ALFWorld and WebShop at both LLM scales, and on Sokoban with a vision-language agent. For example, on ALFWorld it improves overall success rate by up to 24.6 points over GRPO and by up to 4.7 points over the strongest step-level baseline.

Primary area:
reinforcement learning
Keywords:
agentic RL, credit assignment

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_qq1FOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

This paper propose GraphHCA, a model-free hindsight credit assignment method. GraphHCA combines step-level hindsight signal with the trajectory-level advantage, eliminating the explicit hindsight-distribution estimation. GraphHCA achieves best results on ALFWorld, WebShop, and Sokoban.

Critical strengths
  1. The motivation of this paper is clear. The method that combines rollout, constructing state transition and calculate step-level advantage is potentially useful.

  2. The experiments of this paper cover multiple domains and involves a variety of models, which I think is complete.

Critical weaknesses
  1. The presentation of this paper is loose, many parts in this paper are verbose and not informative. For example, authors can merge Figure 1 and 2 to make it more concise; Also, related work and preliminary work repeatedly compare the same set of credit assignment methods. In addition, there are many sentences describing the same thing throughout this article. The authors should consider increasing the information density of the paper to improve its presentation.

  2. The theoretical contribution of this paper is thin, and many propositions are trivial. While I understand some propositions are included to demonstrate the favorable properties of their design methods, I prefer not to bring in too many relatively trivial "propositions". For example, Proposition 4.2 is just a standard contraction result for a discounted Bellman operator. I suggest the author remove these propositions and use simple illustrations to describe these properties.

  3. The improvements shown by GraphHCA on GraphGPO and GiGPO are minor. I'm not sure whether this is a statistically significant improvement, especially considering LLM post-training involves very high variance and results are just averaged with few seeds. Also, the performance trend of each method is identical across all tasks. Though likely possible, I recommend the authors to discuss more about why such consistency is general rather than simply listing the performance numerics. I am not suggesting the author to add experiments on new domains, but I think it would be helpful that they could also include some discussion on when this method can be no longer effective.

Questions for authors
  1. I'm wondering why not having RLOO, PPO RL and the prompting baselines just like Figure 1 (e.g., react) in Figure 2 to keep them consistent?
  2. How are the all success rates in Tables 4 and 5 are computed? Why does Table 5 report 93.3% overall success for the 0.75 discount when the results in Table 4 and 5 imply at least 94.2% under the same subtask weights?
5 comments

We appreciate the reviewer's careful assessment and detailed comments. We have revised the manuscript to address the concerns raised and provide point-by-point responses below.

[W1] Presentation Improvements. We thank the reviewer for this constructive feedback. We have substantially revised the presentation to improve clarity and information density. Specifically, we merged the original Figures 1 and 2 into a unified overview (now Fig. 1), introduced Table 1 to clearly distinguish GraphHCA from existing credit assignment methods, and removed redundant method descriptions from the Preliminaries. We further revised several passages throughout the paper to reduce redundancy and improve clarity and conciseness.

[W2] Refining Theoretical Contributions. We thank the reviewer for this constructive suggestion. We have removed the original Propositions 4.2 and 4.3, incorporating their standard properties directly into the text.

The revised theoretical presentation focuses on two key results. Proposition 4.1 establishes a closed-form characterization of the hindsight ratio in terms of state-wise success probabilities, enabling model-free credit estimation without auxiliary hindsight models or additional policy evaluations. The revised Proposition 4.2 further characterizes the relationship between GraphHCA and GraphGPO, showing that the latter's shortest-path criterion corresponds to best-case aggregation, whereas GraphHCA evaluates expected continuations under empirical transition frequencies. We further illustrate this distinction through a concrete example in Fig. 1(b), contrasting shorter but less reliable paths with longer, more reliable alternatives (Lines 346-350).

These revisions distinguish standard theoretical properties from our central contribution: to the best of our knowledge, the first model-free realization of HCA for LLM agents through a closed-form hindsight ratio, without auxiliary models or additional policy evaluations.

[W3] Statistical Significance, Consistency, and Limitations. We thank the reviewer for these thoughtful comments.

Statistical Significance. We follow the standard evaluation protocol of three random seeds, consistent with GiGPO and GraphGPO. To further assess the reliability of our results, we conduct Welch's t-tests. GraphHCA achieves statistically significant improvements over both baselines on ALFWorld at both model scales (p≤0.035p \leq 0.035) and on WebShop score with the 1.5B model (p≤0.012p \leq 0.012). Beyond these statistically significant gains, GraphHCA matches or exceeds both baselines across all aggregate benchmark metrics, providing further evidence of its effectiveness across diverse settings.

Consistency. We have further clarified the underlying mechanism in the revised Introduction and Sec. 4.4 (Lines 50–90 and 318–354). Unlike GiGPO, which relies on realized rollout returns, and GraphGPO, which favors shortest-path progress, GraphHCA derives a closed-form hindsight ratio in terms of state-wise success probabilities and estimates these probabilities from pooled rollouts, without the additional outcome-conditioned LLM inference required by HCAPO. By aggregating expected continuations under empirical transition frequencies, GraphHCA accounts for how reliably actions lead to success. Proposition 4.2 characterizes the distinction between expected and best-case aggregation, while the ablation in Table 4 shows that replacing expectation with max aggregation reduces ALFWorld success from 95.7% to 90.1%. These findings provide a mechanistic explanation for the observed performance trends.

Limitations. The benefits of GraphHCA depend on informative state sharing across rollouts. When states rarely recur, no successful continuations are observed, or actions from the same state have similar successor potentials, step-level credit becomes sparse or uninformative. Consequently, GraphHCA may offer limited improvements in such settings. We have explicitly discussed these limitations in Appendix F.2 (Lines 1110–1116).

[Q1] Baseline Selection. We thank the reviewer for this comment. Our original baseline selection followed the evaluations in GiGPO and GraphGPO, focusing on GRPO and existing step-level credit assignment methods. To provide a more comprehensive comparison, we have additionally included PPO and RLOO in the revised Table 3. GraphHCA achieves a success rate of 84.0%, outperforming PPO (66.65%), RLOO (66.56%), GRPO (71.1%), GiGPO (79.0%), and GraphGPO (81.6%).

Regarding prompting baselines, the base Qwen2.5-VL model provides a prompting baseline for Sokoban. While ReAct and Reflexion are evaluated in our text-based environments, applying their existing implementations to Sokoban would require adaptation to visual observations. Our primary focus is on evaluating step-level credit assignment, for which comparisons with GRPO, GiGPO, and GraphGPO directly assess the benefits over trajectory-level and existing step-level approaches. The corresponding additions are highlighted in blue in the revised manuscript.

[Q2] Overall Success Rate Calculation. We thank the reviewer for this careful observation. The key distinction is that the overall success rate is computed from task-level results for each seed, rather than as a weighted average of the reported subtask means. Following GraphGPO and GiGPO, we first compute the overall success rate for each seed and then average across three seeds:

Rˉ=13∑s=13∑kSk,s∑kNk,s,\bar{R}=\frac{1}{3}\sum_{s=1}^{3}\frac{\sum_k S_{k,s}}{\sum_k N_{k,s}},

where Sk,sS_{k,s} and Nk,sN_{k,s} denote the numbers of successful and evaluated tasks in category kk for seed ss, respectively.

In contrast, the reported subtask success rates are averaged independently across seeds. Since evaluation tasks are sampled without fixed category quotas, the subtask proportions may vary across seeds. Consequently, a weighted average of the reported subtask means need not equal the overall mean, accounting for the apparent discrepancy at γˉ=0.75\bar\gamma=0.75.

Dear Reviewer,

Thank you again for your valuable feedback. As the discussion period is approaching its end, we would greatly appreciate it if you could let us know whether our rebuttal and additional experiments have addressed your concerns, or if any further clarification is needed.

Thank you for your time and consideration.

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

The paper "GraphHCA: Closed-Form Hindsight Credit Assignment for Long-Horizon LLM Agents" proposes a method for step-level credit assigment for GRPO-like RL methods, which are usually restricted to global/final assessments, without the ability e.g. for crediting good actions in bad trajectories. GraphHCA follows previous attempts as GraphGPO, that construct a pooled graphs from groups of rollouts that share some states. It also takes inspiration from HCAPO that builds on HCA to define step-level advantages based on an estimator of the influence of an action on the final outcome (the hindsight ratio). While HCAPO learns a model of this ratio, GraphHCA proposed to estimate it via a bellman operator on the pooled graph.

Critical strengths
  • Important problem
  • Simple but nice approach to solve the problem
  • Convincing results
  • Some interesting theoretical analyses
Critical weaknesses
  • The reading of the 3 first sections is particularly hard, while the context of the approach is quite simple. The authors use many terms without any definition, assuming the reader is fully aware on their specific problem and the vocabulary of the related litterature (e.g., hindsight ratio). The figure 1, given with very few explanations, is useless in that form. It uses many symbols not yet defined (F, G, etc.) and more importantly, the discussion in the main text is not enough to help the reader understand the important concepts that are presented (please be more descriptive in detailling what is shown on fig 1 (c)). We can say the same for fig 2, especially (d), which lets the reader infer the interpretation by itself. The related work, and especially the main baselines GIGPO, GraphGPO and HCAPO are not enough detailled to allow the reader well analyze the main differences from the reading of the first 3 sections (we better understand latter through).

  • Experiments should give more insights about the impact of the pooled graph structure. I feel it would be very interesting to study the performances evolutions w.r.t. to e.g. the average degree of the graphs, its clustering degree, etc., to better understand in what settings the proposal is useful. Also, this could be connected to the learning state of the agent, since some degrees of learning can correspond to some specific properties for the pooled graph (e.g., while when the policy is fully random the graph many disconnected branches, when it converged to the optimal policy deterministically the graph is a unique branch. it would be nice to study the evolution of graph properties between these two extrema).

  • The approach looks limited to binary final rewards. Could this be extended ?

Questions for authors
  • How are compared states ? I cannot see anything about the criterion used for merging states in the paper. Are the results sensitive to that criterion ?
  • In fig 1 what is the credit assigmenent time ? it is the complexity cost in term of time ? please be more precise
  • What is the impact of structural properties on performances ?
  • How evolves the pooled graph during training ?
  • Authors show that the difference between their approach and GraphGPO is the use of an hindsight potential in theur case and a distance in the case of GraphGPO. Ok but could you please describe settings where this really differs ? in presence of cycles in the pooled graph that's it ? Ok the experiment in table 3 analyses it and gives nice insights, but it would be nice to have intuition before in the paper.
  • In proposition 4.4, c(s,a) is not defined. Please be self-contained (if defined in Cheng et al., 2026), reviewers cannot look at all cited references to understand the concepts and formalism of the paper under review.
  • proposition 4.2 is only the consequence of bellman updates on the pooled graph using your quantities. So it is a very well-known result. You could just mention that bellman contraction applies here, in order to better highlight your own contributions.
10 comments

We thank the reviewer 8y8J for the thoughtful and constructive feedback. We have carefully addressed the concerns raised and revised the manuscript accordingly. Our point-by-point responses are provided below.

[W1] Clarity of Presentation and Figures. We thank the reviewer for these constructive suggestions. We have substantially revised the first three sections to improve conceptual clarity and the presentation of our method.

Conceptual clarity and related work. We have expanded the Introduction (Lines 50–90) to explain key concepts, including foresight, hindsight credit assignment, the hindsight distribution, and the hindsight ratio, before their formal definitions in Sec. 3. We also provide more detailed descriptions of GiGPO, GraphGPO, and HCAPO, and introduce Table 1 (Lines 54–66) to systematically compare their credit assignment principles, evidence sources, and computational overhead.

Figure clarity. We have redesigned and consolidated the original figures into a unified Figure 1, with an expanded caption (Lines 124–131). The revised figure explicitly illustrates rollout graph construction, success-potential estimation, the both trajectory-level and step-level credit assignment. We have also clarified the notation and interpretation of each component to make the method easier to follow. In Fig. 1, FF and GG denote terminal failure state and success state, assigned Φ^(F)=0\hat{\Phi}(F)=0 and Φ^(G)=1\hat{\Phi}(G)=1, which are propagated using empirical transition frequencies. In Fig. 1(d), the trajectory-level advantage is shared across steps, while the step-level advantage standardizes log-potential differences within each source-state group.

These revisions are highlighted in blue in the revised manuscript.

[W2] [Q3] [Q4] We thank the reviewer for this insightful suggestion. To better understand the role of pooled graph structure in GraphHCA, we have added a new analysis in Appendix E (Rollout Graph Dynamics), examining six structural properties and their relationship to policy learning and task performance. The analysis uses Qwen2.5-1.5B-Instruct on ALFWorld.

Graph structure evolution (Q4). As shown in Fig. 4, increasing validation success is accompanied by decreasing mean out-degree, internal branching, and transition entropy, while state sharing increases. Internal clustering rises early and subsequently declines from its early peak. These trends indicate that the rollout graph evolves from a highly branching structure toward more concentrated, shared trajectories as the policy improves. Notably, branching and transition entropy remain nonzero after performance stabilizes, indicating that the learned policy retains some action diversity.

Structure–performance relationship (Q3). Fig. 5 reveals strong correlations between validation success and graph properties, including mean out-degree (r=-0.908), transition entropy (r=-0.953), and internal sharing (r=0.932). These findings also help characterize when GraphHCA provides informative credit: sparse state sharing limits step-level comparisons, whereas near-deterministic policies offer little variation among successor actions. GraphHCA is therefore expected to be particularly informative when sufficient state sharing coexists with differences in successor potentials, enabling discrimination between alternative decisions.

These additional analyses are presented in Appendix E, with the corresponding revisions highlighted in the revised manuscript.

[W3] Extension Beyond Binary Rewards. We thank the reviewer for this important question. Although GraphHCA is originally formulated for binary terminal rewards, its closed-form hindsight formulation can be extended to bounded, non-negative terminal rewards.

Specifically, the success probability in Proposition 4.1 is generalized to the expected terminal reward under the behavior policy. By defining a reward-weighted hindsight distribution, the hindsight ratio retains the same closed-form structure, with the expected reward replacing the success probability. The corresponding log-potential difference and discounted graph recursion remain applicable, with terminal states assigned their observed reward values. The original formulation is recovered when rewards are binary.

We have added a detailed derivation in Appendix F.1 (Lines 1093–1106, Eq. 43), with the corresponding revisions highlighted in blue.

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

This paper proposes GraphHCA, which follows GraphGPO but identifies a main constraint of the shortest-distance potential estimation algorithms used in GraphGPO. To address this, this paper uses HCA to define the potential of states in the graph as hindsight, which involves more information about the rollout conditions. The empirical results show that GraphHCA derives better results compared with GraphGPO.

Critical strengths
  1. This paper introduces a complete theoretical analysis, which helps understand the soundness of the methodology from a theoretical view.
  2. The experiments in closed-ended agentic tasks (where the states are defined by the tasks and states are finite) show a significant advantage compared with baselines.
Critical weaknesses
  1. The motivation "GraphGPO overlooks the modeling of the retrospective relationship" is not completely accurate, because with the shortest-path estimation, better decisions in failed trajectories and a detour or error in a successful trajectory can still be identified.

  2. The writing of this paper is not very clear. For example, the explanation of HCA first appears in Sec. 3, while Sec. 1 broadly uses these concepts. It would be better to make every concept easy to understand in writing.

  3. The success of GraphHCA depends on the reliability of graph construction. When there are ambiguous states (for example, in math agentic reasoning with the Python tool, where each state is a Python execution outcome, a little modification of the code will lead to completely different returns) that are hard to measure for equivalence, the graph-based methods may fail. In addition, it would be better to clarify the applicability of GraphHCA in such agentic reasoning scenarios, which are very popular in current agents.

  4. One important concern of this paper is that it is likely to follow the graph construction setting and only modify the potential estimation algorithms. To me, the contribution is more likely a limited extension of GraphGPO but not a significant advancement in agentic RL.

Questions for authors

See critical weaknesses

11 comments

We thank the reviewer W8ot for the thoughtful and constructive feedback. We have revised the manuscript to address their concerns and provide detailed responses to each comment below.

[W1] Motivation vs. GraphGPO. We thank the reviewer for this comment. GraphGPO, which assigns credit based on shortest-path distance to terminal success states, can indeed identify useful decisions in failed trajectories and detours in successful ones. We agree that our original wording was too broad. The retrospective relationship we refer to is specifically the outcome-conditioned attribution formalized by hindsight credit assignment (HCA). GraphGPO adopts a foresight-based approach that evaluates actions through their best observed continuations, without accounting for how frequently the behavior policy follows them. Consequently, a short but rarely successful path may be favored over a longer but more reliable one. In contrast, GraphHCA derives credit from the HCA hindsight ratio, capturing each action's relevance to eventual success under the behavior policy. To clarify this distinction, we have revised the Abstract (Lines 13–18) and Introduction (Lines 71–77) to more precisely articulate the motivation for GraphHCA. The corresponding revisions are highlighted in blue in the revised manuscript.

[W2] Clarity of Presentation. We thank the reviewer for this helpful suggestion. We agree that HCA should be explained in the Introduction before it is used to motivate our method. We have therefore revised the Introduction (Lines 78–90) to introduce HCA intuitively before its formal definition in Sec. 3. Specifically, we explain that HCA compares the probability of an action conditioned on eventual success with its probability under the behavior policy. We then define the hindsight distribution and hindsight ratio, and explain that a ratio above or below one indicates that the action increases or decreases the chance of success, respectively.

To make the relationship between methods easier to follow, we also clarify the distinction between foresight and hindsight credit assignment in the Introduction (Lines 50–90) and add Table 1 (Lines 54–65) to compare their credit granularity, attribution principles, evidence sources, and computational overhead. The Abstract and Fig. 1 have also been revised to summarize the motivation and provide an overview of the GraphHCA workflow, respectively. The corresponding textual revisions are highlighted in blue in the revised manuscript.

[W3] Graph Reliability and Agentic Reasoning Applicability. We thank the reviewer for raising this important concern.

Reliability of graph construction. We first clarify the distinction between states and actions in GraphHCA. Actions represent agent decisions, while states are represented using environment-derived observations. In the reviewer's Python-based reasoning example, code snippets constitute actions, whereas their execution results provide observations for constructing successor states. Thus, code changes that produce different execution results may lead to distinct successor states. GraphHCA does not require determining the semantic equivalence of different code snippets; instead, it constructs a shared transition graph by grouping state representations across trajectories.

In our main experiments, GraphHCA employs hash-based matching to group identical state representations (Lines 372–374). However, identifying equivalent states remains challenging in complex tool-use environments. Unreliable state representations or matching criteria may either fail to identify equivalent states or incorrectly merge distinct ones, resulting in insufficient state sharing or inaccurate credit assignment. We have further clarified these limitations in Appendix F.2 of the revised manuscript.

Applicability to agentic reasoning. To further evaluate GraphHCA in tool-augmented reasoning, we conducted additional experiments on seven search-augmented QA datasets using Qwen2.5-3B-Instruct (Table 8, Appendix D.3), with the results reproduced below in Table 1. Unlike our main experiments, which use hash-based exact matching, the SearchQA experiments follow GiGPO's similarity-based grouping with a threshold of 0.9 to mitigate sparse state sharing caused by variations in textual observations. GraphHCA achieves the best performance on five of the seven datasets and the highest average accuracy of 43.8%, compared with 43.5% for HCAPO, 42.8% for GraphGPO, 42.1% for GiGPO, and 32.5% for Search-R1. Together, these results demonstrate the effectiveness of GraphHCA under both exact and approximate state-matching settings and extend its empirical validation to search-augmented agentic reasoning. The corresponding additions and revisions are highlighted in blue in the revised manuscript.

Table 1. Performance on SearchQA tasks with Qwen2.5-3B-Instruct. † and * indicate in-domain and out-of-domain datasets, respectively. Bold indicates the best performance.

MethodNQ†TriviaQA*PopQA*HotpotQA†2Wiki*MuSiQue*Bamboogle*Avg.
R1-Instruct27.053.719.923.729.27.229.327.1
Search-R134.154.537.832.431.910.326.432.5
ZeroSearch41.457.444.827.430.09.811.131.7
GiGPO42.059.542.436.937.012.664.142.1
HCAPO44.460.545.538.636.314.864.543.5
GraphGPO44.559.746.236.237.212.163.742.8
GraphHCA (Ours)45.762.146.637.437.612.764.743.8

Comments on the paper

1 comment
Area_Chair_Zq16OpenReview ↗

Please engage with authors

Dear Reviewers,

The author-reviewer discussion will be closed on November 18 (AoE). If you haven’t yet replied to the authors’ latest response, please do so on OpenReview as soon as possible so they have time to follow up. A brief reply indicating which of your concerns have been addressed and what questions remain would be helpful. Thank you for your time and for engaging with the authors.

Best regards,

AC

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.