AgentHER: Hindsight Experience Replay for LLM Agent Trajectory Relabeling
Organizations: The University of Sydney
Abstract
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
Figures & tables
| WebArena WA-HeldOut (%) | ToolBench pass@1 (%) | |||||||
| Method | GPT-4o | Qwen-72B | Qwen-7B | LLaMA-8B | GPT-4o | Qwen-72B | Qwen-7B | LLaMA-8B |
| Base | 13.7 | 20.9 | 8.2 | 6.5 | 53.2 | 60.1 | 44.6 | 42.1 |
| SFT-Random ‡ | 18.0 | 25.6 | 13.9 | 12.7 | 61.4 | 68.9 | 54.8 | 52.9 |
| SFT-Negative | 18.6 | 26.1 | 14.5 | 13.1 | 62.1 | 69.5 | 55.6 | 53.7 |
| Rejection-Sampling | 20.7 | 28.6 | 16.9 | 15.5 | 66.2 | 73.7 | 59.8 | 57.4 |
| SFT-Success | 22.3 | 29.9 | 17.8 | 16.4 | 67.8 | 75.4 | 61.2 | 58.3 |
| Stage | Calls /tr. | Cost ($) | Wall (m) |
| S1 detector | 1.00 | 0.39 | 4.1 |
| S2 extractor | 1.00 | 0.55 | 4.6 |
| S3a relabeler | 1.27 | 0.84 | 6.7 |
| S3b verifier (MJ-X only) | 1.00 | 1.20 | 10.1 |
| S4 augmenter (det.) | — | 0.00 | 0.4 |
| SJ total | 3.27 | 1.78 | 15.8 |
| Configuration | Success (%) | Noise (%) | |
| Full AgentHER-MJ-X (cross-model judge severity) | 26.5 | — | 2.9 |
| w/ Same-model multi-judge (MJ-S, two temps) | 26.0 | 0.5 | 4.4 |
| w/o Multi-judge (single judge only, AgentHER-SJ) | 25.7 | 0.8 | 5.9 |
| w/o Severity weighting ( for all) | 25.0 | 1.5 | 4.3 |
| w/ Rule-based Extractor (Stage 2 degraded) | 24.6 | 1.9 | 6.0 |
| w/ LLM Detector (Stage 1 upgraded) | 27.4 | 0.9 | 2.4 |
| Failure type | WebArena | ToolBench |
| Incomplete | 32.4% | 21.0% |
| of which looping | 12.1% | 4.5% |
| Constraint_Violation | 30.7% | 17.6% |
| Wrong_Result | 17.6% | 23.7% |
| Tool_Error | 4.2% | 25.4% |
| Hallucination | 7.0% | 8.5% |
| WebArena | ToolBench | |||
| Group | n | Valid (%) | n | Valid (%) |
| SJ accepted | 169 | 94.1 | 168 | 92.3 |
| MJ-S accepted | 142 | 95.6 | 138 | 94.0 |
| MJ-X accepted | 137 | 97.1 | 132 | 96.0 |
| Filter-rejected | 31 | 38.7 | 32 | 35.8 |
| Fleiss’ | — | 0.82 | — | 0.79 |
| Round | Src. | New fails | Accepted | Suc. (%) |
| 0 (SFT-Only) | — | — | — | 17.8 |
| 1 (MJ-X) | GPT-3.5 | 3,000 | 2,144 | 26.5 |
| 2 (Iter. +1) | Q-R1 | 2,500 | 1,710 | 27.9 |
| 3 (Iter. +2) | Q-R2 | 2,000 | 1,320 | 28.2 |
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
| Role | Stage | Model | Notes |
| Collection agent | — | gpt-3.5-turbo-0125 | Intentionally weak. |
| Failure detector | 1 (LLM) | gpt-4o-mini | , JSON schema. |
| Outcome extractor | 2 (LLM) | gpt-4o-mini | , factuality-only. |
| Relabeler | 3 | gpt-4o-mini | ; on retry. |
| Verifier (MJ-X) | 3 | Qwen2.5-72B-Instruct | , vLLM, schema-constrained. |
| Verifier (MJ-S) | 3 | Qwen2.5-72B-Instruct | Ablation only; same as at . |
| Hyperparameter | SFT (LoRA) | DPO (LoRA) |
| LoRA rank | 16 | 16 |
| LoRA | 32 | 32 |
| LoRA dropout | 0.05 | 0.05 |
| LoRA target modules | q,k,v,o,gate,up,down | q,k,v,o |
| Learning rate | ||
| LR schedule | cosine | cosine |
| Method | Full (812) | HeldOut (200) | Drop |
| Base | 8.6 | 8.2 | 0.4 |
| SFT-Success | 18.9 | 17.8 | 1.1 |
| ETO | 22.1 | 21.0 | 1.1 |
| AWM | 23.4 | 22.4 | 1.0 |
| AgentHER-SJ | 27.0 | 25.7 | 1.3 |
| AgentHER-MJ-X | 27.8 | 26.5 | 1.3 |
| Category | Base | SFT-Random | SFT-Success | AgentHER-SJ | AgentHER-MJ-X |
| G1 (single-tool) | 49.3 | 57.2 | 67.1 | 76.4 | 77.9 |
| G2 (intra-category) | 41.7 | 51.3 | 58.3 | 68.5 | 70.0 |
| G3 (cross-category) | 38.2 | 47.8 | 54.2 | 65.0 | 66.6 |
| Overall | 44.6 | 54.8 | 61.2 | 71.0 | 72.6 |
| Failed processed | 500 | 1,000 | 1,500 | 2,000 | 3,000 | 5,000 |
| AgentHER-SJ | 20.0 | 21.5 | 22.9 | 23.9 | 25.7 | 26.4 |
| AgentHER-MJ-X | 20.6 | 22.2 | 23.7 | 24.7 | 26.5 | 27.2 |
| Method | G1 | G2 | G3 | Overall | |
| Base (no FT) | 49.3 | 41.7 | 38.2 | 44.6 | — |
| SFT-Success | 63.2 | 55.8 | 51.4 | 57.1 | 12.5 (vs. Base) |
| AgentHER-SJ | 70.1 | 64.3 | 59.8 | 65.0 | 7.9 (vs. S-S) |
| AgentHER-MJ-X | 71.8 | 65.9 | 61.4 | 66.6 | 9.5 (vs. S-S) |
| Subset | n | Recoverable (%) | Accepted (%) | Avg. (%) |
| Looping (WebArena) | 363 | 24.2 | 21.5 | 3.4 |
| Non-looping (WebArena) | 2,637 | 81.6 | 78.4 | 9.5 |
| Looping (ToolBench) | 225 | 38.7 | 35.1 | 3.9 |
| Non-looping (ToolBench) | 4,775 | 84.6 | 81.7 | 10.7 |
| Method | Mean | Std |
| Base | 8.2 | 0.0 (deterministic) |
| SFT-Success | 17.8 | 0.3 |
| SFT-Random | 13.9 | 0.4 |
| SFT-Negative | 14.5 | 0.4 |
| Rejection-Sampling | 16.9 | 0.4 |
| ETO | 21.0 | 0.4 |
| Stage | Model | Calls / traj. | Inp tok | Out tok | Cost (USD) | Wall (s) |
| 1: Failure detector | gpt-4o-mini | 1.00 | 1,800 | 200 | 0.82 | |
| 2: Outcome extractor | gpt-4o-mini | 1.00 | 2,500 | 300 | 0.92 | |
| 3a: Relabeler | gpt-4o-mini | 1.27 | 2,700 | 400 | 1.34 | |
| 3b: Verifier (MJ-X) | Qwen2.5-72B | 1.00 | 3,000 | 200 | 1.94 | |
| 4: Data augmenter | deterministic | 1.00 | — | — | 0 | 0.08 |
| SJ total | — | 3.27 | — | — | 3.16 |
| Metric | S-S | AgentHER |
| Task clusters covered (of 18) | 11 | 14 |
| Long-tail clusters (unique) | 0 | 3 |
| JS divergence (vs. AgentHER) | 0.31 | — |
| Avg. cluster entropy | 1.83 | 2.47 |