acceptodds
Under review as a conference paper at ICLR 2027

ECHO-Graph: Scaling Long Horizon RL with Dependency-Aware Credit Propagation

Abstract

Long-horizon agentic reinforcement learning requires not only extending the accessible interaction history, but also assigning effective learning signals across repeatedly reconstructed contexts. ECHO couples context management with credit assignment by selecting historical memories during reconstruction and reinforcing the turns retained in the final reconstruction trace. However, final-trace masking on successful trajectories can leave early prerequisite steps unreinforced as reconstruction depth grows, biasing learning toward later stages. Fully masking unsuccessful trajectories removes corrective feedback, risking rapid entropy collapse and reduced exploration. We propose ECHO-Graph, which propagates outcome credit backward through a DAG of turn dependencies induced by context reconstruction, reinforcing early prerequisite steps and repeatedly reused evidence in successful trajectories. For unsuccessful trajectories, where provenance does not reliably support fine-grained credit assignment, we apply attenuated dense penalties to provide corrective feedback and help sustain exploration. The method requires no additional rollouts, critics, or model evaluations. Experiments on BrowseComp-Plus and SWE-Bench Pro show gains over ECHO, especially on difficult instances, with stronger context-horizon scaling on the former.

Primary area:
reinforcement learning
Keywords:
Agentic RL, Tool-Using Agents, Long-Horizon Reasoning, Credit Assignment, Turn-Memory Graphs

Reviews

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

ECHO-Graph extends ECHO, which rebuilds agent context from selected past turns, rewards only the final reconstruction trace, and masks failures. It adds (i) a dependency DAG over successful trajectories with discounted credit propagated backward from the terminal turn, and (ii) attenuated dense GRPO-style negative advantages on failures. Experiments on curated subsets of BrowseComp-Plus and SWE-Bench Pro report gains over ECHO and ablations.

Critical strengths

S1. Credit assignment across repeated reconstructions is a real gap, and the observation that final-trace masking leaves early prerequisite turns unreinforced is sound.

S2. Modeling cross-reconstruction dependencies explicitly as a DAG and propagating credit over it without additional rollouts, critics, or model evaluations is a reasonable direction.

Critical weaknesses

W1. [Motivation] The motivation does not hold. Entropy collapse is not a credit-assignment phenomenon. ECHO masks every failed trajectory, so all advantages are positive and each update only sharpens the policy. The paper's own results confirm this (entropy goes to zero at λneg=0 and rises with λneg, Figure 3(c). Negative credit alone raises entropy while graph credit alone accelerates its decline, in Section 5.3. Entropy coefficient 0 and KL disabled Appendix). The paper presents this artifact as a research problem and restoring negative samples as a contribution. The second limitation, limited horizon gains, rests on one or two questions out of fifty in Figure 1(a). The need for a dependency graph is not clear.

W2. [Method] The edge construction is unjustified and self-contradictory. Edges are the policy's own selection records and adjacency. No argument is given to justify that selected turns contribute, or that unselected turns do not, yet the latter receive only geometrically decaying chain credit. The paper acknowledges provenance is "a proxy for contribution rather than a guarantee of causal relevance" (Section 4.3) and "does not reliably identify" credit-worthy decisions on failures (Section 4.2), but contradictorily relies on it for successes. The paper should state the principle under which selection implies contribution, its conditions, and a formal relation between Eq. (8) credit and counterfactual contribution, instead of only providing edge definitions and the elementary bound in Eq. (11). Absent this, any favourable result may be a coincidence specific to the selected datasets.

W3. [Method] The reported gains are attributable to λneg rather than to the graph. Positive advantages are scaled by credits below one while negative advantages are scaled by a fixed coefficient. Token-level advantages are therefore no longer centered within a group, and every update carries a net sign bias determined jointly by γ and λneg. The entropy dynamics follow this bias alone. Entropy vanishes at λneg=0, remains low at 0.5, and rises sharply at 1.0 in Figure 3(c). The accuracy differences across these settings follow the same pattern. The paper does not separate the effect of this bias from the effect of graph structure, so the improvements it reports can be explained by the negative-feedback weight without reference to the dependency graph.

W4. [Experiments] The evaluation does not support the claims. First, the paper lacks direct evidence that graph-assigned credit reflects actual contribution. This requires validation against an independently defined and reproducible ground truth, demonstrating that credited turns are necessary for the outcome while uncredited turns are not. Section 4.4 only examines credit magnitudes and does not establish this correspondence. Second, the reliability of the reported gains remains unclear. The evaluation sets also serve to select the coefficient, aggregation rule, and checkpoint (Sections 4.4 and 5), which introduces potential selection bias. Select Agent + GRPO, the baseline implied by the paper's own motivation, is absent from Table 1. Results are confined to author-curated subsets of 50 instances per level, evaluated with a single seed, with difficulty defined by rollouts of an unspecified model. The gains should be established on the full benchmarks, on data uninvolved in any design or checkpoint choice, against Select Agent + GRPO, and with improvements exceeding run-to-run variance. Finally, the method is presented as a general framework for long-horizon agentic RL, yet no evidence is given that it works beyond the setting in which its design choices were tuned.

Questions for authors

Q1. Are the validation sets used to select the coefficient, aggregation rule, and checkpoint identical to the Table 1 evaluation sets?

Q2. Does Select Agent + GRPO with λneg=0.8 match ECHO-Graph? This determines whether the gains come from the graph or from the negative-feedback weight.

Q3. What fraction of training rollouts involve at least one reconstruction? Without reconstruction, the graph is a chain, and the method reduces to discounted dense credit.

5 comments

Thank you for setting out the value you see in this work and for the new horizon runs. The three-seed BCP gains over ECHO exceed the seed standard deviations at all levels, and the new horizon runs show ECHO-Graph ahead of dense positive credit at every level and horizon. My main concerns, however, are not fully resolved.

  1. I read the method as a joint scheme of graph credit and dense negative feedback, and I accept that dense negative feedback at the chosen λneg does not achieve the gains on its own, which answers my Q2. The reported reconstruction fractions also address my Q3. What remains open from W3 is whether the dependency graph structure itself matters. The new horizon runs show that the margin over dense positive credit is not specific to one horizon. Like the sequential-only run, however, each is a single run that differs from ECHO-Graph both in how positive credit is propagated across turns and in the total positive credit each successful rollout receives, so none of them isolates the effect of the graph structure. The λneg and checkpoint selection rule used in these runs are not stated. Two controls would separate the propagation of positive credit from its total amount, both at the same λneg and each matched to ECHO-Graph in token-weighted total positive advantage per rollout. The first is a sequential discount whose rate is set per rollout to reach that total. The second keeps the graph but connects each selection edge to a random earlier turn, with the rate set per rollout in the same way. If ECHO-Graph clearly outperforms both over the same seeds under the protocol in point 2 below, the dependency graph structure itself matters on BCP. On SWE-Bench Pro, where the gain over ECHO currently rests on a single run, the same comparison even with a single shared seed would show whether this holds beyond BCP.

  2. Following up on Q1, the reported gains are measured on the same questions that are used to select checkpoints and, on BCP, to compare λneg values. This applies to the trained results in Table 1, Figure 6, and the three-seed runs, and each Figure 6 horizon is a single run. The larger last-checkpoint advantage mentioned to Reviewer F12S comes without specific numbers. Selecting the checkpoint on one half of the questions in each level and reporting on the other half, averaged over many random splits, for the existing runs including SWE-Bench Pro, the three-seed runs, each Figure 6 horizon and the new horizon runs, would show whether the gains hold without checkpoint-selection bias. The same split applied to the Figure 3(d) runs would do the same for λneg, and neither requires new training.

  3. Regarding W2, my earlier wording on per-turn necessity may have been unclear. I did not mean that training should verify every credited turn, which would be computationally impractical, and I agree that such a check would not by itself establish that the overall scheme works. My point is that ECHO-Graph, unlike GRPO, is designed to credit turns based on their role in the dependency graph, so it is fair to ask whether its credit tracks contribution better than a sequential discount. The argument that unselected turns are not directly necessary explains why they should receive less credit than selected turns, but not why the amounts should follow the clipped discounted sums of Eq. (8), and Section 4.3 treats provenance as a proxy for contribution without defining what contribution means. The paper should formally state what quantity Eq. (8) approximates and under which conditions, or show on a few successful rollouts with at least one memory selection that removing turns ranked higher by graph credit than by sequential credit reduces the success rate more than removing turns ranked lower. Specifically, each turn would be removed from the memory and all later contexts, and the drop in success rate would be measured over several samples of the rest of the rollout from the next memory selection, relative to the same sampling without the removal. It would also help to state how graph credit would apply when context is managed without explicit selection records, as in the Summary Agent of Table 1.

AuthorsOpenReview ↗

Additional Baselines: Validating the Effectiveness of the Graph Structure

We understand that the reviewer would like to examine the effect of the credit-assignment structure while keeping positive and negative training signals comparable.

The balance between positive and negative gradients also depends on how often the current policy succeeds. Even if we fix λneg\lambda_{\mathrm{neg}} and match the token-weighted total positive advantage per successful rollout, different credit-assignment methods may learn at different rates and produce different proportions of successful rollouts. These two constraints therefore cannot hold the overall gradient balance fixed throughout training. We use policy entropy to compare how concentrated the policies become as training progresses, as Reviewer F12S also suggested. For the original ECHO-Graph run, we retained evaluation checkpoints, but not the per-rollout selection records needed to recover its training-time credit totals.

To address your concern, we designed the following comparisons:

  • Random-connect. We replace the selection edges with edges to random earlier turns and keep the rest of the graph unchanged. We use four random connections per selection, based on the average number of turns selected per event in evaluations of the initial and final ECHO-Graph checkpoints. We keep λneg=0.8\lambda_{\mathrm{neg}}=0.8.
  • Sequential-only. Our earlier sequential-only control used the same λneg=0.8\lambda_{\mathrm{neg}}=0.8 as ECHO-Graph. Here we keep the same sequential discount and set λneg=0.65\lambda_{\mathrm{neg}}=0.65 to target ECHO-Graph’s entropy trajectory.

BCP results are reported as mean ± SD over three training seeds (7, 14, and 42), as in our previous experiments. Except for the settings specified above, the experiments below use split-half evaluation, with results averaged over three splits.

MethodBCP EasyBCP MediumBCP HardSWE EasySWE Hard
Random-connect (4 per selection)0.80 ± 0.040.38 ± 0.050.10 ± 0.030.67 ± 0.050.19 ± 0.04
Sequential-only, λneg=0.65\lambda_{\mathrm{neg}}=0.650.80 ± 0.030.32 ± 0.040.06 ± 0.030.63 ± 0.020.13 ± 0.02

Sequential-only shows limited gains on BCP Medium and Hard and SWE-Bench Pro Hard. Random-connect improves over sequential-only on these levels, reaching performance close to ECHO. Its BCP results also vary somewhat more across seeds, possibly due to the additional randomness in edge selection. These results suggest that the specific dependency structure matters for ECHO-Graph’s gains.

AuthorsOpenReview ↗

A Formal Interpretation of Graph Credit and Eq. (8)

We believe the random-connect and sequential-only results above support the role of the graph. We also welcome the opportunity to explain the design of Eq. (8) in more detail.

Our gold-doc recall analysis provides evidence that the selector retains relevant information, supporting the emphasis on selected turns. The graph is designed to address two questions: how to distinguish the importance of selected turns, and how to assign credit to unselected turns.

Credit for selected turns. A turn selected multiple times is reused across multiple stages of reasoning and receives credit from multiple paths. We take this repeated selection as evidence that the turn has an important role in the successful trajectory. This is the main reason for using sum aggregation.

Max aggregation can propagate credit to selected turns, but it only keeps the largest incoming credit and cannot emphasize repeated selection. Moreover, credit may continue to decay as it propagates backward, favoring later turns in a way similar to sequential-only discounting.

Unclipped sum aggregation has a different difficulty. With weak discounting, credit can accumulate excessively at nodes where paths converge, which we found harmful in practice. Stronger discounting prevents this inflation, but it also reduces the credit reaching earlier convergence points, making them harder to distinguish from other turns. The appropriate discount can therefore depend on trajectory length and task difficulty. Clipping credit at 1 is a practical way to balance these effects: it allows multiple paths to highlight reused turns while preventing their credit from growing without bound.

Credit for unselected turns. Unselected turns lack selection records that indicate their relevance. To assign credit without additional evaluations, we use temporal proximity as a signal of local support.

For example, when reconstructing context, agent harnesses often retain recent turns alongside selected or compressed history. Recent turns provide details about the agent’s current progress; removing them can force the agent to reconstruct that progress and repeat tool calls. Similarly, the preceding turn will generally provide more direct support for the current step than a turn from dozens of steps earlier. This motivates discounting credit as it propagates backward.

How discounting and aggregation work together. Discounting spreads credit to earlier turns, while aggregation identifies turns supported by multiple paths and increases their credit before it is propagated further backward. Without aggregation, continued discounting increasingly favors turns near the end of the trajectory, regardless of whether earlier turns were repeatedly selected. Both the selection behavior and our sequential-only results suggest that temporal distance alone is insufficient.

Under this interpretation, Eq. (8) gives each turn a bounded measure of its structural support for the successful reasoning trajectory. This interpretation relies on the selector tending to retain relevant information, repeated selection indicating reuse, and nearby turns providing stronger local support.

Reviewer_Y8WjOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

ECHO-Graph propagates positive credit through context-reconstruction dependencies and combines it with attenuated dense negative feedback for long-horizon agent training. My concerns are that (i) the novelty and necessity of dependency-aware graph propagation are not sufficiently established. (ii) the claim that negative feedback improves exploration is not sufficiently supported, since it also changes the balance between positive and negative gradients.

Critical strengths
  1. The paper is clear and the method is easy-to-understand.
Critical weaknesses
  1. The novelty and necessity of dependency-aware graph propagation are not sufficiently established. Although component-level ablations are provided, comparisons with dense positive supervision, sequential-only discounting, and shuffled dependency edges are missing, making it difficult to distinguish the benefits of dependency structure from broader supervision coverage.
  2. The claim that negative feedback improves exploration is not sufficiently supported, since it also changes the balance between positive and negative gradients. Higher entropy and accuracy alone do not establish this mechanism; clarifying token-level loss normalization and reporting effective positive/negative weights and update magnitudes would help distinguish exploration benefits from changes in optimization scale.
Questions for authors
  1. Could you compare the proposed propagation rule with dense positive supervision, sequential-only discounting, and shuffled dependency edges to isolate the benefits of the actual dependency structure?
  2. Are the main results evaluated on an independent test set that was not used for hyperparameter tuning or checkpoint selection? Please clarify the data splits and selection procedure.
  3. Do the hard-subset improvements persist across independent training seeds? Could you provide paired instance-level comparisons and confidence intervals?
  4. Do the long-horizon gains persist under matched token or wall-clock budgets? Please report generated tokens, tool calls, and training time across horizon settings.
  5. How is the token-level loss normalized after masking and reweighting? Could you report effective positive/negative weights and update magnitudes to distinguish improved exploration from changes in optimization scale?
1 comment

Dear Reviewer Y8Wj,

As we have not yet heard back on our rebuttal, we would appreciate it if you could take a moment to review our response and our follow-up discussion with Reviewer QoTq.

We have clarified the relationship between policy gradients and entropy dynamics, as well as the goal of the horizon-scaling experiment. We have also added GRPO scaling results, random-connect and sequential-only baselines, split-half and last-checkpoint evaluations, and a detailed explanation of the graph-credit design.

We hope these explanations and additional results address your concerns and help you make a fair assessment of our work. Thank you for your time.

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

The paper extends ECHO, an agentic RL framework that routes outcome credit only to turns retained in the final context-reconstruction trace. It identifies two failure modes: early prerequisite turns lose reinforcement as reconstruction depth grows, and fully masking failed trajectories removes corrective feedback, causing entropy collapse. ECHO-Graph builds a DAG of turn dependencies induced by reconstruction (sequential, recent-turn continuity, selection-induced, selection-action edges) and propagates terminal credit backward with discount γ\gamma, sum aggregation, and unit clipping. For failures it applies attenuated dense penalties λneg⋅A^\lambda_{neg} \cdot \hat{A} to all trainable tokens. The method needs no extra rollouts, critics, or model evaluations, and propagation is O(∣V∣+∣E∣)O(|V|+|E|).

Credit-design analyses motivate γ=0.9\gamma=0.9 and λneg=0.8\lambda_{neg}=0.8, avoiding both entropy collapse (λneg≤0.5\lambda_{neg} \leq 0.5) and explosion (λneg=1.0\lambda_{neg} =1.0). On BrowseComp-Plus and SWE-Bench Pro it improves over ECHO by 10.4 points Pass@1 on average, with the largest gains on hard instances. Ablations show graph credit alone accelerates entropy decline while dense negative credit alone raises entropy without helping harder tasks, supporting the joint-design hypothesis. A 64K →\rightarrow 768K scaling study shows ECHO-Graph keeps converting longer horizons into accuracy where ECHO saturates. Appendices provide configs, prompts, and qualitative analyses.

Critical strengths

S1. Analysis-driven joint design: Both components are derived from empirically substantiated failure modes (Fig. 1), and the ablation directly supports the claim that negative feedback only helps harder tasks when paired with broader positive-credit coverage — a useful insight beyond this specific method.

S2. Efficiency: Credit propagation reuses ECHO's existing provenance at O(|V|+|E|) cost, with no extra rollouts or critics, making adoption cheap and the controlled comparison clean.

S3. Gains where theory predicts: Improvements concentrate on hard instances and grow with reconstruction depth and context horizon, directly evidencing the central claim rather than a diffuse average gain.

Critical weaknesses

W1. Statistical reliability of headline numbers. 50-instance subsets, no seed variance or confidence intervals, and best-checkpoint selection; e.g., Hard goes 0.10 →\rightarrow 0.18, i.e. 5 →\rightarrow 9 correct, plausibly within RL noise. The 10.4-point average may therefore be materially overstated.

W2. Missing controls. No other credit-assignment method is evaluated, and -- more consequentially -- no standard exploration-maintenance baseline (entropy bonus, clip-higher, KL regularization) is compared. Since dense negative credit on failed tokens partly acts as an adaptive entropy regularizer, the ablation does not rule out that graph credit plus any entropy maintenance performs similarly.

W3. Unvalidated proxy and sensitive heuristics. Provenance is used as a stand-in for causal contribution (acknowledged, but never checked, e.g. via counterfactual turn ablation), and the graph embeds several ad hoc choices (continuity edge, selection-action proxy, γ\gamma, clipping). Fig. 3 shows sensitivity to λneg\lambda_{neg} (0.5 collapses, 1.0 destabilizes), and dense penalties also punish genuinely useful early turns in failed rollouts.

Questions for authors

Q1. How many seeds underlie Table 1 and Figs. 4–6? Please report variance, especially on Hard (n=50), and confirm best-checkpoint selection was applied identically to baselines.

Q2. Did you compare against ECHO + entropy bonus (or clip-higher) at matched entropy trajectories? This seems essential for attribution.

Q3. Did you try routing negative credit through the DAG or restricting it to the final segment before resorting to dense penalties? What failed?

Q4. Were γ=0.9\gamma=0.9 and λneg\lambda_{neg}=0.8 re-validated on SWE-Bench Pro or transferred from BrowseComp-Plus?

Q5. Do conclusions hold under last-checkpoint or fixed-epoch evaluation?

1 comment
AuthorsOpenReview ↗

Response to Reviewer F12S

Dear Reviewer F12S,

As we have not yet heard back on our rebuttal, we would appreciate it if you could take a moment to read our follow-up discussion with Reviewer QoTq. In addition to the entropy-bonus comparison in our earlier response, we have provided GRPO scaling results, random-connect and sequential-only baselines, split-half and last-checkpoint evaluations, and a detailed explanation of the graph-credit design.

If these additions help address your concerns, we would appreciate it if you would consider raising your score.

Thank you for your time.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.