PaperlayerView exact revision on arXiv

Source-linked AI summary

AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling

Liang Ding

arXiv:2603.21357v4cs.AIcs.CL

TL;DR

LLM-agent training commonly discards failed trajectories, leaving much collected data unused. AgentHER relabels failures as demonstrations for alternative goals; on WebArena and ToolBench it improves over success-only SFT by +7.6–11.4% across four model families.

  • Problem

    Standard agent-training pipelines discard failed trajectories, wasting collected data despite failures that may contain correct intermediate work for a different goal.

    Source: §1 · p. 1

  • Method

    AgentHER adapts goal-conditioned hindsight experience replay to offline natural-language trajectories, relabeling failures as valid demonstrations for synthesized alternative goals.

    Source: §1 · p. 1, §3.1 · p. 3

  • Results

    +7.6–11.4% over SFT-Success across four model families on a strict task-disjoint WebArena held-out split and ToolBench.

    Source: §6 · p. 8

  • Takeaways & Limitations

    The paper’s conclusion is that success versus failure is task-relative, not trajectory-absolute.

    Source: §6 · p. 8

    Evaluation covers only two benchmarks and does not resolve cross-environment generalization.

    Source: §6 · p. 8

Abstract

from arXiv · show

LLM-agent training pipelines routinely discard failed trajectories even though GPT-4o achieves only 14-20% on WebArena and below 55% pass@1 on ToolBench; even specialised systems at 50-65% leave the majority of trajectories unused. We introduce AgentHER, which recovers this lost signal by adapting Hindsight Experience Replay (HER) to natural-language agent trajectories: a trajectory that fails goal A is often a correct demonstration for an achievable alternative goal B. AgentHER realises this through a four-stage pipeline (failure classification, outcome extraction, LLM-guided relabeling with confidence gating, and data packaging) that converts discarded failures into SFT, DPO, and ShareGPT training data. On WebArena and ToolBench under a strict task-disjoint held-out protocol, AgentHER improves over success-only SFT by +7.6-11.4% across four model families (GPT-4o, Qwen2.5-72B/7B, LLaMA-3.1-8B), achieves 2x sample efficiency, and beats the strongest experience-centric baseline (Agent Workflow Memory) by +3.0-6.2%. Two robustness mechanisms, failure-severity weighting and cross-model multi-judge verification (gpt-4o-mini paired with Qwen2.5-72B-Instruct), reduce label noise from 5.9% to 2.9% and raise human-rated relabeling precision to 97.1% on WebArena and 96.0% on ToolBench. A full system-cost audit shows the entire relabeling pipeline costs 2.98 and 26 wall-clock minutes for 3,000 trajectories, i.e. 1.4 x 10^-3 per accepted pair. Code: https://github.com/alphadl/AgentHER

1 Introduction

AgentHER turns failed LLM-agent trajectories into training examples for achievable alternative goals, using quality controls to limit label noise. On WebArena and ToolBench, it improves held-out performance over success-only SFT and the strongest experience-centric baseline.

1 Introduction

  • Standard pipelines discard 60–75% of collected data, although failed trajectories can contain coherent executions that achieve correct intermediate results under a different goal.For example, comparing suppliers and finding one just above a price cap can be useful training signal for a reframed goal.Source: §1 · p. 1
  • 5.9% to 2.9% label noise reduction comes from failure-severity weighting and cross-model multi-judge verification, which raises precision to 97.1% on WebArena and 96.0% on ToolBench.Both gpt-4o-mini and Qwen2.5-72B-Instruct must accept a relabeling; severity weighting drops trajectories with major reasoning flaws.Source: §1 · pp. 1–2
  • AgentHER adapts goal-conditioned HER to natural-language trajectories in an offline pipeline that produces SFT, DPO, and ShareGPT data without extra environment interactions.Its four stages automate hindsight relabeling; the method must infer what multi-step tool interactions achieved and synthesize a prompt the trajectory satisfies.Source: §1 · p. 1
  • +7.6–11.4% over SFT-Success on a strict task-disjoint held-out split; AgentHER also exceeds the strongest baseline, AWM, by +3.0–6.2%.Gains hold across 1.5B–72B parameters (+5.6–9.0%) and compound under iterative redeployment (+10.4% over four rounds).Source: §1 · p. 2
  • $2.98 and 26 wall-clock minutes cover relabeling 3,000 trajectories, with 3.27–4.27 LLM calls per trajectory.The introduction presents this audit as evidence that sample-efficiency gains are not offset by pipeline overhead.Source: §1 · p. 2

2 Related Work

AgentHER adapts hindsight relabeling to offline LLM-agent training by identifying what a failed trajectory achieved and generating a natural-language goal it satisfies. Related work distinguishes this approach from runtime planning, other forms of experience reuse, and inference-time scaling.

Hindsight Experience Replay

  • HER relabels sparse-reward failures with goals actually achieved, but LLM agents also require extracting outcomes from tool interactions and synthesizing natural-language goals (Andrychowicz et al., 2017).Earlier NLP failure-reuse methods select or reweight existing goal–trajectory pairs rather than generate a new achievable goal.Source: §2 · p. 2

LM-agent adaptations of HER

  • Unlike ECHO’s online scratchpad planner, AgentHER performs offline data augmentation by relabeling only goals and leaving trajectories unchanged (Hu et al., 2025).It packages the relabeled data for SFT, DPO, or ShareGPT; the paper compares against an offline-faithful ECHO reimplementation in Section 4.2.Source: §2 · p. 2

Experience-centric agent learning

  • Experience-centric methods use inference-time rules, matched success/failure DPO pairs, successful workflows, or online verbal RL; AgentHER converts failures offline without extra interactions or matched successes.The cited examples are ExpeL (Zhao et al., 2024), ETO (Song et al., 2024), AWM (Wang et al., 2024), and Reflexion (Shinn et al., 2023); AgentHER’s standard SFT/DPO data can combine with these methods.Source: §2 · p. 2

Self-improvement, verification, and critique

Test-time compute and inference scaling

  • Inference scaling improves pass@k through repeated trials, whereas AgentHER reduces per-task failure probability through training data, making the two approaches complementary (Levi, 2024).The paper describes AgentHER as strengthening the base model offline, after which test-time compute can extract additional coverage.Source: §2 · pp. 2–3

3 The AgentHER Framework

AgentHER turns failed agent trajectories into training pairs by extracting achieved outcomes, synthesizing factual alternative goals, and accepting only sufficiently verified relabelings. Its four-stage pipeline filters failures, extracts outcomes, relabels and verifies goals, then packages accepted pairs into training formats.

3.1 Problem Formulation

  • AgentHER maps failed runs to accepted hindsight goal–trajectory pairs or rejection, requiring goals to be observation-supported and judged valid by two independent LLMs.Accepted pairs augment the existing corpus with up to one labeled pair per failed run.Source: §3.1 · p. 3

3.2 Pipeline Overview

  • The four-stage pipeline processes failed trajectories using rule-based or LLM-judge variants in Stages 1–2, two independent LLM calls in Stage 3, and deterministic packaging in Stage 4.The rule-based variants in Stages 1–2 are zero-cost.Source: §3.2 · p. 3, Figure 2 · p. 4

3.3 Stage 1: Failure Detector

  • Failure detection assigns a type, recoverability flag, and severity weight; discarding major errors and weighting minor ones reduces noisy relabelings from 5.9% to 2.9%.Major-error runs with weight below δ = 0.3 are discarded, while severity weights also scale the DPO loss.Source: §3.3 · p. 3

3.4 Stage 2: Outcome Extractor

  • The outcome extractor records achievements and key observations as factual anchors for relabeling, helping prevent hallucinated hindsight prompts.Rule-based extraction treats non-trivial, non-error observations as achievements; the LLM variant can summarize implicit results and deduplicate facts.Source: §3.4 · p. 3

3.5 Stage 3: Cross-Model Relabeling and Verification

  • Cross-model verification accepts a relabeled goal only when independently trained judges both meet the confidence threshold; it retries up to three times and retains a qualifying single-judge fallback.The default cross-model configuration pairs gpt-4o-mini with Qwen2.5-72B-Instruct.Source: §3.5 · p. 4

3.6 Stage 4: Data Augmenter

  • Stage 4 serializes each accepted goal–trajectory pair into SFT, DPO, and ShareGPT formats.Severity weight scales the SFT loss and DPO reward margin; DPO pairs the hindsight goal as chosen against the original goal as rejected.Source: §3.6 · p. 4

3.7 Theoretical Plausibility

  • Under a perfect judge, every accepted pair is a correct goal–trajectory sample from the oracle policy’s support; with cross-model precision p = 0.971, the noisy-judge gain bound is positive when ε ≤ 33 · Δperfect.For the single-judge precision p = 0.941, the corresponding condition is ε ≤ 16 · Δperfect.Source: §3.7 · p. 4

4 Experiments

AgentHER turns failed LLM-agent trajectories into useful training data and improves benchmark performance under a strict task-disjoint evaluation. The experiments also examine judge independence, system cost, data efficiency, model scale, ablations, and qualitative relabeling examples.

4.1 Experimental Setup

  • The evaluation uses a strict task-disjoint WebArena split and collects 3,000 failed and 500 successful WA-TRAIN trajectories, alongside 5,000 failed and 2,000 successful ToolBench trajectories.SFT-Random uses the same 3,000 WebArena failures as AgentHER without relabeling, providing an equal-volume control.Source: §4.1 · pp. 4–5

4.2 Main Results

  • MJ-X outperforms SJ by +0.8–1.6% and MJ-S by +0.5%, showing greater benefit from model-level independence than temperature diversity alone.7B/8B models gain +10.7–11.4% on ToolBench versus +8.1% for Qwen-72B and +7.6% for GPT-4o. SFT-Negative gains only +0.4–0.8% over SFT-Random, versus AgentHER’s +12–18% (WebArena: +12–13%; ToolBench: +14–18%); WA-TRAIN training also yields +9.5% over SFT-Success zero-shot on ToolBench.Source: §4.2 · p. 5

4.3 System Cost Analysis

  • Relabeling costs $1.4×10^-3 per accepted pair; MJ-X’s multi-judge overhead is +$1.20 (+67%) and +9.7 min (+61%).That overhead accompanies a precision increase from 94.1% to 97.1% and a downstream gain of +0.8–1.6%. The combined relabeling-plus-LoRA budget is $7.18 / 4.8 h.Source: §4.3 · p. 5, Table 2 · p. 6

4.4 Data Efficiency and Scaling

  • AgentHER-SJ reaches full-SFT-Success performance using only 50% of successful demonstrations, while MJ-X exceeds it at every data point.Performance scales log-linearly with failure volume, and the optimal threshold θ∗=0.5 is consistent across both variants.Source: §4.4 · p. 5

4.5 Model-Size Scaling

  • Across five Qwen2.5 checkpoints from 1.5B to 72B, AgentHER-MJ-X’s gain peaks at +9.0% on 14B and is +7.8% on 72B.The 1.5B model improves from 6.4% to 12.0%.Source: §4.5 · p. 5

4.6 Ablation Study

  • Cross-model MJ-X cuts label noise from 4.4% to 2.9%; removing confidence filtering drops performance by 4.2% and raises noise to 15.0%.Severity weighting accounts for −1.5%; naive relabeling harms performance by −6.1%, and DPO preference pairing contributes −2.5% over SFT.Source: §4.6 · pp. 5–6

4.2 Main Results

  • AgentHER-MJ-X improves over SFT-Success by 7.6–8.7% on WebArena and 7.6–11.4% on ToolBench, beating experience-centric baselines by +3.0–6.2%.The comparison uses WebArena’s strict task-disjoint WA-HELDOUT split and ToolBench’s official test splits.Source: §4.2 · p. 5, Table 1 · p. 6

4.7 Qualitative Examples

  • The qualitative appendix presents two annotated CONSTRAINT_VIOLATION relabeling examples, one each from WebArena and ToolBench.The examples include original failed goals and trajectories, accepted hindsight goals, and cross-model judge rationales.Source: §4.7 · p. 6

5 Analysis

AgentHER recovers useful signal from different failure types, produces precise and complementary hindsight goals, and continues to improve through iterative redeployment. Its benefits vary with failure type, data volume, and model scale.

5.2 Per-Failure-Type Improvement on Both Benchmarks

  • INCOMPLETE yields +11.0% / +12.7% and CONSTRAINT_VIOLATION +9.6% / +11.0% on WebArena / ToolBench, while TOOL_ERROR yields +2.0% / +1.8%.The two highest-gain types make up ≈63% of WebArena failures versus ≈38% of ToolBench failures; the ranking holds across benchmarks.Source: §5.2 · p. 6, Figure 5 · p. 8
  • At 50% of successful demonstrations, AgentHER-SJ matches SFT-Success at 100%, while AgentHER-MJ-X exceeds it.Both AgentHER variants scale log-linearly with failure volume, whereas SFT-Success does not benefit from additional failures; both peak near θ*=0.5.Source: Figure 3 · p. 7

5.1 Failure-Mode Distributions on Both Benchmarks

  • ToolBench has 6× the TOOL_ERROR rate and WebArena 1.7× the CONSTRAINT_VIOLATION rate; looping trajectories are 12.1% of WebArena failures.Stage 1 rejects 76% of looping trajectories; the remaining 24% yield +3.4% over SFT-Success, versus +9.5% for non-looping trajectories.Source: §5.1 · p. 6, Table 4 · p. 7

5.3 Judge Reliability and Label Quality (Both Benchmarks)

  • 97.1% / 96.0% precision for cross-model multi-judge relabelings on WebArena / ToolBench comes with Fleiss’ κ=0.82 / 0.79.Same-model multi-judge reaches 95.6% / 94.0%; filter-rejected pairs are 38.7% / 35.8% valid.Source: Table 5 · p. 7, §5.3 · pp. 7–8
  • On WA-HELDOUT, AgentHER-MJ-X gains are consistent across Qwen2.5 model sizes from 1.5B to 72B, peaking at +9.0% for 14B.The 1.5B model improves from 6.4% to 12.0%.Source: Figure 4 · p. 8

5.4 Goal-Distribution Analysis

  • AgentHER covers 14 of 18 task-type clusters versus 11 for SFT-Success, including three long-tail clusters covered only by relabeled goals.The relabeled goals have JS divergence 0.31 from the original goal set, indicating complementary rather than redundant coverage.Source: §5.4 · p. 8

5.5 Iterative Redeployment

  • 26.5% in Round 1 is followed by gains of +1.4% and +0.3% in Rounds 2–3, for a cumulative +10.4% over SFT-Success.Acceptance falls from 71.5% to 68.4% to 66.0% as the model produces harder, less-relabelable failures.Source: Table 6 · p. 8, §5.5 · p. 8

6 Conclusion

AgentHER repurposes failed agent trajectories as training data and improves results on held-out WebArena and ToolBench tasks. The conclusion also outlines future extensions, evaluation limits, and potential broader impact.

6 Conclusion

  • +7.6–11.4% over SFT-Success and +3.0–6.2% over ETO, ECHO-offline, and AWM on strict task-disjoint WebArena and ToolBench.Results scale from 1.5B to 72B (+5.6–9.0%) and compound to +10.4% over four redeployment rounds; relabeling costs ≈$1.4·10−3 per accepted pair ($2.98 / 26 min for 3,000 trajectories).Source: §6 · p. 8
  • Future directions include online relabeling during deployment, multimodal trajectories, learned hindsight-goal synthesis, and combining AgentHER with inference-time scaling (Levi, 2024).AgentHER frames success and failure as task-relative rather than trajectory-absolute; reducing per-sample failure probability pi may amplify inference-scaling coverage gains under a fixed budget.Source: §6 · p. 8
  • Evaluation remains limited by cross-environment uncertainty, only two benchmarks, no fully matched human-written-goal upper bound, and possible residual cross-model judge bias on rare tasks.The +9.5% WA→ToolBench transfer is encouraging but covers only two benchmarks; the judge relies on two strong LLMs.Source: §6 · pp. 8–9
  • Reusing collected trajectories without extra environment interaction may reduce fine-tuning data costs for resource-constrained practitioners, but deployers should monitor goal-distribution drift.Stratified human evaluation and goal-distribution analysis partially mitigate the risk that systematic judge bias amplifies underrepresented goal types.Source: §6 · p. 9

A Hyperparameter Settings and Roles of Each LLM … D Additional Experimental Results

The appendix specifies model roles, operational prompts for detecting and relabeling failed trajectories, and severity-weighted DPO settings.

A Hyperparameter Settings and Roles of Each LLM

  • Collection uses a weak model to produce diverse failures, while judging uses strong, architecturally independent models.GPT-4o fine-tuning used defaults (3 epochs, auto-selected batch size, learning-rate multiplier 1.0); GPT-4o-ICL uses 8 relabeled exemplars selected by sentence-BERT cosine similarity and prepended to a chain-of-thought ReAct prompt, without fine-tuning.Source: Table 7 · p. 11, A Hyperparameter Settings and Roles of… · p. 11

B.1 Stage 1 — Failure Detection

  • Stage 1 classifies failures by type, assesses recoverability, and assigns severity weights below 0.3 to major errors and 0.3–1.0 to minor errors.Failure types are constraint_violation, wrong_result, incomplete, tool_error, hallucination, and off_topic; trajectories with substantive observations are recoverable, while crashes with no output are not.Source: §B.1 · p. 11

B.2 Stage 2 — Outcome Extraction

  • Stage 2 extracts a strictly factual summary of achievements, successful tool use, information gathered, and numeric observations from the trajectory.The prompt prohibits inference or extrapolation beyond directly evidenced trajectory observations.Source: §B.2 · p. 12

B.3 Stage 3 — Relabeler J1 (gpt-4o-mini)

  • Relabeler J1 turns the outcome summary into a plausible new user prompt that the trajectory perfectly satisfies and assigns a confidence score.It must not reuse the failed prompt, should match its complexity and style, and outputs validity, rationale, and confidence from 0.0 to 1.0.Source: §B.3 · p. 12

B.4 Stage 3 — Verifier J2 (Qwen2.5-72B-Instruct)

  • Verifier J2 independently and conservatively accepts a proposed prompt only when every claim is unambiguously supported by the trajectory observations.The verifier is instructed not to defer to the relabeler and returns validity, confidence, and any rejection reason.Source: §B.4 · p. 12

C AgentHER Algorithm with Severity Weighting

  • Severity-weighted DPO uses per-sample weights of 0.3–1.0, β = 0.1, and the same instruction-tuned checkpoint before LoRA as its reference model.Continuous scaling preserves binary preference ordering while down-weighting borderline relabelings; the full pseudocode is identified as Algorithm 1 in the main paper.Source: C AgentHER Algorithm with Severity… · p. 12

D.1 Held-Out vs. Full-Task Numbers … D.7 Theoretical Bound (Full)

The appendix reports that AgentHER’s advantage over success-only SFT is stable between full-task and held-out WebArena evaluation, and presents cross-benchmark transfer and theoretical support for relabeling. It also specifies the human-evaluation protocol and bounds the effect of noisy judges under stated assumptions.

D.1 Held-Out vs. Full-Task Numbers

  • +8.9% on Full and +8.7% on HeldOut are AgentHER’s respective gains over SFT-Success, with the relative ranking stable across protocols.The Full evaluation uses the original 812 tasks; HeldOut uses a 200-task task-disjoint split. The passage characterizes the difference between Full and HeldOut numbers as at most 1.3% in absolute terms.Source: §D.1 · p. 12, Table 9 · p. 13

D.6 Human Evaluation Protocol (Full)

  • Three blind annotators rated 200 relabeled pairs sampled per benchmark for whether each trajectory correctly and completely demonstrated its hindsight prompt.Sampling was stratified across six failure types and the looping sub-mode; annotators saw the trajectory and hindsight prompt but not the original prompt, failure reason, or confidence scores.Source: §D.6 · p. 13

D.7 Theoretical Bound (Full)

  • Under a perfect judge, every added pair is a previously uncovered oracle pair, and augmented-corpus goal entropy is higher with probability 1 − δ when |F| ≥ 2δ log |Gϵ|.The proof argues that hindsight goals arise from observed execution contexts and differ from the original goals; redundant additions are not harmful, while diverse failed goals support entropy growth.Source: §D.7 · p. 13

D.4 Cross-Benchmark Transfer

  • +9.5% transfer advantage over SFT-Success is reported for AgentHER-MJ-X in zero-shot ToolBench evaluation after training on WebArena.The transfer is described as suggesting broadly applicable planning and tool-use behaviors rather than rote task patterns.Source: §D.4 · p. 13, Table 12 · p. 14

D.7 Theoretical Bound (Full)

  • For judge precision p, expected gain is p ∆perfect − (1 − p) ε and is positive when ε ≤ p/(1 − p) ∆perfect.The stated thresholds are ε ≤ 33 ∆perfect at p = 0.971 and ε ≤ 16 ∆perfect at p = 0.941; the bound assumes i.i.d. judge errors and bounded marginal harm, so it is not a deployment guarantee.Source: §D.7 · p. 14
  • The bound is consistent with the reported entropy increase from 1.83 to 2.47 nats and MJ-X’s +0.8% empirical advantage over SJ on WA-HELDOUT.These findings are presented as empirical support for the theoretical result, not as a deployment guarantee.Source: §D.7 · p. 14

E Multi-Run Variance · F Detailed Cost Breakdown

AgentHER’s multi-run training results are numerically stable, with standard deviations below 0.5%. For 3,000 trajectories, the relabeling pipeline costs about $2.98 and takes about 26 minutes with parallelism; including LoRA fine-tuning, the total is $7.18 and 4.8 hours.

E Multi-Run Variance

  • Across three independent random seeds, all reported standard deviations for representative WA-HELDOUT conditions are below 0.5%.Table 1 fine-tuned models use seeds 42, 1234, and 2025 with the same data and hyperparameters; reported numbers are means.Source: E Multi-Run Variance · p. 14

F Detailed Cost Breakdown

  • For 3,000 trajectories, MJ-X relabeling costs about $2.98 and takes about 25.9 minutes with 12-way concurrency.The SJ pipeline costs about $1.78 and takes about 15.8 minutes under the same conditions.Source: F Detailed Cost Breakdown · p. 14
  • Per accepted pair, MJ-X costs $1.39×10^-3 at 71.5% acceptance, versus SJ at $7.6×10^-4 and 78.0% acceptance.MJ-X costs roughly 1.8× as much because the second-judge call applies to every candidate, including rejected ones.Source: F Detailed Cost Breakdown · p. 14
  • The 3,000-trajectory project totals $7.18 and 4.8 hours when subsequent LoRA fine-tuning is included.This combines $2.98 of LLM API spend with $4.20 of A100 GPU time; the passage compares the total cost with 200 fresh WebArena rollouts using GPT-4o.Source: F Detailed Cost Breakdown · p. 14

G Qualitative Examples

Two annotated examples show AgentHER turning failed WebArena and ToolBench trajectories into accepted hindsight demonstrations by relaxing constraints that the collected evidence could not satisfy.

WebArena example

  • On WebArena, the empty ≥30-days-stale subset caused a minor CONSTRAINT_VIOLATION (w=0.82), but the 11-issue trajectory was recoverable.AgentHER-MJ-X accepted a broader goal to list the assigned open issues with labels and update dates (c1=0.86, c2=0.91); both judges confirmed the 11 returned issues satisfied it.Source: G Qualitative Examples · pp. 14–15

ToolBench example

  • On ToolBench, the search found no Michelin-starred Italian restaurants in Hangzhou (w=0.78), and AgentHER-MJ-X accepted a goal to recommend a best-rated vegan-menu option.The trajectory returned 14 restaurants, none Michelin-starred; the judges confirmed that the revised goal no longer required Michelin status or opening after 9 pm.Source: G Qualitative Examples · p. 15

H Goal-Distribution Analysis (Full)

AgentHER-MJ-X expands goal-distribution coverage beyond the 500 original successful goals, adding long-tail clusters and complementary semantic coverage.

H Goal-Distribution Analysis (Full)

Related papers

Loading 2603.21357v4…