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 pipelines discard most failed trajectories despite modest success rates, leaving potentially useful experience unused. AgentHER relabels failures with achievable natural-language goals through an offline pipeline, improving held-out results across models while increasing sample efficiency and controlling label noise. The paper reports practical relabeling cost, but its transfer evidence covers only two benchmarks and a human-written hindsight-goal upper bound remains future work.

  • Problem

    Standard LLM-agent training pipelines discard 60–75% of collected failed trajectories even though failures can contain correct intermediate results under alternative goals.

  • Method

    AgentHER uses an offline four-stage pipeline to extract achieved outcomes, relabel goals with LLM guidance and confidence gating, and package unchanged trajectories into SFT, DPO, and ShareGPT data.

  • Results

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

  • Takeaways & Limitations

    AgentHER recovers training signal from failed trajectories, achieving 2× sample efficiency and practical relabeling cost while outperforming experience-centric baselines.

  • Takeaways & Limitations

    Transfer evidence covers only WebArena and ToolBench, and a fully matched human-written hindsight-goal upper bound remains future work.

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 reframes failed agent trajectories as training data for achievable alternative goals, addressing the 60–75% of collected data discarded by conventional pipelines. Its relabeling and quality-control mechanisms improve held-out performance while expanding usable data at measured cost.

  • Motivation: 60–75% of collected trajectories are discarded by standard pipelines, although failures often contain correct intermediate results under a different goal.A trajectory identifying a supplier just above a price cap can support a reframed comparison goal.
  • Approach: AgentHER adapts HER to natural-language agent trajectories by extracting achieved outcomes and synthesising prompts that the unchanged trajectories satisfy.The offline pipeline produces SFT, DPO, and ShareGPT datasets without additional environment interactions.
  • Quality control: Failure-severity weighting and cross-model multi-judge verification reduce relabeling label noise from 5.9% to 2.9%.The two judges are gpt-4o-mini and Qwen2.5-72B-Instruct, and both must accept a relabeling.
  • Efficiency: ≈3.7× effective corpus expansion costs ≈$1.4·10−3 per accepted pair.The full audit reports $2.98 and 26 wall-clock minutes for 3,000 trajectories.
  • Results: 94.1% to 97.1% relabeling precision is achieved on WebArena, with 96.0% on ToolBench.These figures quantify human-rated precision after the quality-control mechanisms.
  • Results: +7.6–11.4% over SFT-Success on a strict task-disjoint held-out split across four model families.AgentHER also exceeds the strongest baseline by +3.0–6.2%.

2 Related Work

Related work spans hindsight relabeling, experience-centric learning, verification, and inference-time scaling. AgentHER differs by performing offline goal-only relabeling of unchanged multi-step trajectories for training-data augmentation.

  • Hindsight Experience Replay: HER relabels sparse-reward failures with the goal actually reached, whereas LLM-agent adaptation must interpret unstructured tool interactions and synthesise satisfying natural-language prompts.These requirements extend beyond substituting a vector-space goal.
  • LM-agent adaptations: ECHO adapts HER online by rewriting goals and intermediate steps, while AgentHER performs offline augmentation and changes only the goal.AgentHER packages the resulting data as SFT, DPO, and ShareGPT datasets.
  • Experience-centric learning: Experience-centric methods include inference-time rules, matched-pair DPO, workflow-memory induction, and online verbal reinforcement learning.Other fine-tuning systems primarily curate successful trajectories.
  • Verification: Prior verification approaches use tool-augmented critics, process reward models, or same-model self-consistency, providing contrasts for AgentHER’s multi-judge design.The supplied passage identifies these as operating on single-step text, reasoning steps, or aggregated same-model samples.
  • Inference scaling: Inference scaling improves pass@k through repeated trials, whereas AgentHER targets the per-sample failure probability through offline training-data improvement.The paper presents the two mechanisms as complementary.

3 The AgentHER Framework

AgentHER turns failed agent runs into training data by extracting achieved outcomes, synthesizing validated hindsight goals, and packaging accepted pairs for multiple supervision formats. Its design filters major flaws, verifies relabelings across independently trained models, and formally characterizes the effect of judge noise.

  • Problem formulation: AgentHER maps failed runs to valid hindsight-goal demonstrations or rejects them, expanding successful data with accepted relabeled pairs.A hindsight goal must be factually supported by trajectory observations and accepted by two independent judges above threshold θ.
  • Pipeline overview: The four-stage pipeline detects failure type and severity, extracts achieved outcomes, relabels with confidence gating, and serializes accepted pairs.Stages 1–2 support rule-based variants, while Stage 3 uses relabeling and verification loops and Stage 4 is deterministic.
  • Failure detection and severity weighting: Major-error trajectories receive w < δ = 0.3 and are discarded, while minor-error trajectories proceed with severity-weighted downstream training.This weighting distinguishes contradictions, hallucinated observations, and catastrophic tool misuse from incomplete or constraint-violation cases.
  • Cross-model relabeling and verification: Cross-model verification requires gpt-4o-mini and Qwen2.5-72B-Instruct to independently assign confidence at least θ before acceptance.The protocol is intended to reflect inter-model consensus rather than same-model self-consistency, with up to K = 3 relabeler attempts.
  • Data augmentation: Accepted pairs are exported as SFT, DPO, and ShareGPT data, with severity weights scaling SFT loss and DPO reward margins.The DPO representation pairs the hindsight-goal trajectory with the original failed-goal trajectory as the rejected example.
  • Theoretical plausibility: Under a perfect judge, every accepted pair is a correct goal–trajectory sample; with precision p, the expected gain is p · ∆perfect − (1 − p) · ε.For p = 0.971, the supplied bound is positive when ε ≤ 33 · ∆perfect; this is presented as a plausibility argument rather than a deployment guarantee.

4 Experiments

Experiments evaluate AgentHER under task-disjoint protocols across WebArena and ToolBench, multiple model families, baselines, scaling conditions, and system-cost constraints. AgentHER consistently improves over success-only training and experience-centric alternatives while using failures more efficiently.

  • Experimental Setup: Evaluations use strict task-disjoint collection and held-out testing, with results averaged over three seeds and standard deviations below 0.5 points.WebArena uses 612 collection tasks and 200 held-out tasks; ToolBench covers official training and test splits.
  • Main Results: Cross-model multi-judge AgentHER outperforms single-judge by +0.8–1.6% and same-model multi-judge by +0.5%.Model-level independence provides a larger benefit than temperature diversity alone.
  • Data Efficiency: AgentHER-SJ matches full SFT-Success performance with 50% of successful demonstrations, while AgentHER-MJ-X exceeds SFT-Success across the tested data points.Both AgentHER variants scale log-linearly with failure volume, whereas SFT-Success cannot leverage additional failures.
  • Model Scaling: AgentHER-MJ-X gains remain positive from 1.5B to 72B parameters, peaking at +9.0% for the 14B Qwen2.5 model.The 1.5B model rises from 6.4% to 12.0% under AgentHER-MJ-X.

5 Analysis

Analysis examines which failures are most recoverable, how relabeling components affect performance and noise, and whether gains generalize across task types, scales, and iterative rounds. The strongest benefits come from informative failures, confidence control, and cross-model verification.

  • Failure Types: Looping failures comprise 12.1% of WebArena failures; retained looping trajectories gain +3.4%, below non-looping failures at +9.5%.Stage 1 rejects 76% of looping trajectories because they contain no useful intermediate state.
  • Failure Types: INCOMPLETE and CONSTRAINT_VIOLATION failures yield the largest gains, while TOOL_ERROR failures yield the least on both benchmarks.INCOMPLETE gains are +11.0/+12.7% and CONSTRAINT_VIOLATION gains are +9.6/+11.0% on WebArena/ToolBench; TOOL_ERROR gains are +2.0/+1.8%.
  • Component Ablations: Removing the confidence filter drops performance by 4.2% and raises relabeling noise to 15.0%, while naive relabeling drops performance by 6.1%.These ablations show that acceptance control and goal reverse-engineering are central to AgentHER’s gains.
  • Judge Reliability: Cross-model MJ-X reaches 97.1% precision on WebArena and 96.0% on ToolBench, exceeding same-model MJ-S precision of 95.6% and 94.0%.Human evaluation used 200 sampled pairs per benchmark and three annotators with majority voting.
  • Goal Coverage: AgentHER covers 14 of 18 task-type clusters versus 11 for SFT-Success, with three long-tail clusters covered only by relabeled goals.A JS divergence of 0.31 from the original goal set indicates complementary rather than redundant coverage.
  • Iterative Improvement: Iterative redeployment adds +10.4% cumulatively, but later rounds show diminishing returns and acceptance rates fall from 71.5% to 68.4% to 66.0%.The declining acceptance rate reflects increasingly capable models producing harder, less-relabelable failures.

6 Conclusion

AgentHER reframes failed agent trajectories as reusable training data through offline hindsight relabeling. Across held-out benchmarks, it improves performance and offers low-cost reuse, while cross-environment generalization and judge bias remain bounded concerns.

  • +7.6–11.4% over SFT-Success across four model families on task-disjoint WebArena and ToolBench splits.
  • +3.0–6.2% over every experience-centric baseline, including ETO, ECHO-offline, and AWM.
  • $1.4·10^-3 per accepted pair makes the relabeling pipeline practical at production scale.For 3,000 trajectories, the audit reports $2.98 and approximately 26 wall-clock minutes.
  • The held-out evaluation covers only two benchmarks and does not remove cross-environment concerns.A fully matched upper bound using human-written hindsight goals remains future work.
  • Residual judge bias may amplify underrepresented goal types despite human evaluation and goal-distribution analysis.Deployers are advised to monitor goal-distribution drift on their own data.

A Hyperparameter Settings and Roles of Each LLM

The appendix specifies the LLM roles, GPT-4o settings, trajectory-analysis prompts, verifier prompt, and severity-weighted DPO configuration used by AgentHER.

  • LLM roles: Collection uses a weak model for diverse failures, while judging uses strong, architecturally independent models.
  • Hyperparameters: GPT-4o fine-tuning uses 3 epochs, automatically selected batch size, and learning-rate multiplier 1.0.The reproducible GPT-4o-ICL variant instead uses 8 similarity-selected hindsight-relabeled exemplars without fine-tuning.
  • Pipeline prompts: Failure detection classifies failure type, recoverability, and severity before downstream relabeling.The classifier distinguishes substantive recoverable trajectories from crashed runs with no output and major reasoning flaws.
  • Pipeline prompts: Outcome extraction summarizes only concrete facts, successful tool calls, gathered information, and numeric observations evidenced by the trajectory.
  • Pipeline prompts: Relabeling generates a plausible new user prompt that every trajectory assertion must satisfy, then returns validity, rationale, and confidence.
  • Pipeline prompts: The independent verifier accepts only prompts whose claims are unambiguously supported by the recorded observations.It is instructed not to defer to or echo the relabeler.
  • Training configuration: Severity weighting uses wi ∈[0.3, 1.0], β = 0.1, and a pre-LoRA instruction-tuned reference model in the DPO loss.

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

Held-out evaluation preserves AgentHER’s advantage over full-task and baseline comparisons, while transfer results and theoretical analysis provide supporting evidence for broader coverage and robustness.

  • Held-out versus full-task results: +8.9% on Full versus +8.7% on HeldOut, with all Full–HeldOut differences at most 1.3 percentage points.The relative ranking remains stable, so the reported gains are not attributed to task overlap.
  • Held-out versus full-task results: The official ToolBench test splits are disjoint by construction and are reported by category group for Qwen2.5-7B.
  • Cross-benchmark transfer: +9.5% transfer advantage over SFT-Success is reported for AgentHER-MJ-X.The passage interprets this out-of-domain result as evidence of broadly applicable planning and tool-use behaviours rather than rote task patterns.
  • Evaluation protocol: Human evaluation samples 200 relabeled pairs per benchmark, with three blind annotators rating complete and correct demonstrations.The original failed prompt and failure reason were withheld from annotators.
  • Theoretical analysis: Under a perfect judge, added pairs are previously uncovered valid oracle pairs and increase empirical goal-distribution entropy with probability 1 −δ.The theorem’s entropy guarantee applies when the failure set satisfies the stated covering-number condition.
  • Theoretical analysis: For judge precision p = 0.971, the noisy-judge bound permits marginal harm ε ≤33 ∆perfect while retaining positive expected gain.
  • Theoretical analysis: The bound assumes i.i.d. judge errors and bounded marginal harm, making it a plausibility argument rather than a deployment guarantee.

E Multi-Run Variance

Repeated training runs show low numerical variance, while the cost audit quantifies the relabeling and fine-tuning resources required for a typical 3,000-trajectory project.

  • Multi-run variance: All standard deviations are below 0.5% across three independent random seeds.The reported values are means using seeds 42, 1234, and 2025.
  • Cost audit: $2.98 and approximately 25.9 minutes cover the MJ-X relabeling pipeline for 3,000 input trajectories.The corresponding per-accepted-pair cost is $1.39×10^-3 after 71.5% acceptance.
  • Cost audit: $7.18 and 4.8 hours cover relabeling plus subsequent LoRA fine-tuning for a typical 3,000-trajectory project.This total includes $4.20 of A100 GPU time and is reported as less than 200 fresh WebArena rollouts with GPT-4o.

G Qualitative Examples

The examples show AgentHER recovering failed constraint-based tasks by extracting correctly gathered results and relabeling them to achievable goals. Cross-model judges accept both relabelings when the failed constraints are removed.

  • Pipeline: The qualitative examples illustrate AgentHER’s complete Stage 1–3 pipeline on CONSTRAINT_VIOLATION failures from WebArena and ToolBench.The examples include failure classification, trajectory outcomes, hindsight goals, and cross-model judge rationales.
  • WebArena: 11 open GitLab issues with labels were recovered from a failed task whose stale-issue filter matched no issues.The trajectory collected the issue data correctly, making the failure recoverable.
  • WebArena: The GitLab relabeling was accepted after independent confirmation by gpt-4o-mini and Qwen2.5-72B.Both judges confirmed that the required issue attributes were present and the stale filter was no longer required.
  • ToolBench: A restaurant-search failure was relabeled to recommend a best-rated Italian restaurant in Hangzhou with a vegan menu.The original trajectory found highly rated Italian restaurants, a vegan menu, and opening hours despite failing the Michelin-star constraint.
  • ToolBench: The restaurant relabeling was accepted because the Michelin-star and late-opening constraints were absent from the hindsight goal.The cross-model rationale treats those removed constraints as vacuously satisfied.

H Goal-Distribution Analysis (Full)

AgentHER-MJ-X produces relabeled goals with broader semantic coverage than original successful goals, including three long-tail clusters absent from success-only SFT. The analysis also reports the relabeling cost structure and collection statistics.

  • Goal coverage: Three long-tail clusters—price-range comparison, cross-domain search, and conditional retrieval—appear only among AgentHER-MJ-X relabeled goals.The analysis compares 2,144 accepted hindsight goals with 500 original successful goals.
  • Goal coverage: A JS divergence of 0.31 indicates complementary rather than redundant coverage between accepted hindsight goals and original successful goals.The comparison uses Sentence-BERT embeddings of the two goal collections.
  • Cost analysis: Table 15 breaks down token counts and per-trajectory calls by relabeling stage under discounted batch pricing, caching, and batched Qwen deployment assumptions.The listed pricing is production-oriented, while standalone gpt-4o-mini list pricing is approximately twice as high.
  • Goal coverage: Table 16 analyzes semantic task-cluster coverage on the WA-HELDOUT collection, contrasting AgentHER-MJ-X with SFT-Success.The table specifically reports clusters uniquely covered by relabeled goals.
Loading 2603.21357v4…