The Reinforcement Learning (RL) paradigm has achieved remarkable success in enhancing the reasoning capabilities of Large Language Models (LLMs). However, when applied to long-horizon tasks, it faces severe challenges: i) Due to the high task complexity, the model struggles to sample enough successful trajectories, resulting in slow convergence. ii) Relying solely on sparse final rewards causes all steps to be updated indiscriminately, encouraging redundant step generation. When both the quantity and quality of successful trajectories become difficult to guarantee, the performance is severely constrained. This dilemma stems from the limitations: existing RL paradigms rely entirely on the reasoning capability of base models, lacking the ability to actively optimize trajectories. To address the above issues, we propose a novel trajectory evolution paradigm with hindsight credit assignment, termed TrajEvolve. TrajEvolve not only relies on the trajectory inferred by the model but also generates ``evolutionary trajectories'' by refining low-quality steps in historical trajectories, thereby exposing the policy to high-quality compositions that lie within the base model's support but are rarely sampled within practical training budgets. Furthermore, TrajEvolve reformulates step-level continuous credit assignment as a binary classification task, whether each step is necessary for task completion. This simplification not only reduces the learning difficulty but also enables step labels to be obtained through counterfactual verification, achieving precise identification of redundant steps. Extensive experiments on two datasets demonstrate the superiority of the proposed method.
Figures & tables
Figure 1: Overview of the TrajEvolve training framework. Left: Training pipeline with hindsight verification and trajectory evolution module. Right: Three trajectory evolution strategies.
Type
Method
ALFWorld
WebShop
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Succ.
Closed-Source Model
Prompting
GPT-4o
81.3
25.0
36.3
38.5
40.7
23.1
45.3
30.8
18.8
Prompting
Gemini-2.5-Pro
83.3
42.9
48.6
54.5
64.7
42.9
57.8
42.8
26.6
Qwen2.5-1.5B-Instruct
Prompting
Qwen2.5
11.1
0.0
7.1
0.0
0.0
7.7
5.5
22.4
5.5
Table 1: Performance Comparison on ALFWorld and Webshop benchmarks. Results are averaged over 3 random seeds. For ALFWorld, we report the success rate (%) for the results. For WebShop, we report both the average score and the success rate (%).
Figure 2: Validation success rate during training on ALFWorld and WebShop dataset.
Figure 3: Effect of integrating the trajectory evolution module with different RL baselines. The shaded area indicates the performance gain from adding our evolution module.
Model
ALFWorld
WebShop
Avg. Steps
Succ. Steps
Avg. Steps
Succ. Steps
PPO
17.45
10.63
8.94
8.61
RLOO
15.20
10.06
7.98
7.11
GRPO
15.36
11.26
10.97
12.61
GiGPO
11.58
8.76
6.16
5.33
Ours
9.63
7.91
5.89
5.15
Table 2: Redundancy analysis on ALFWorld and WebShop. “Avg. Steps” denotes mean steps across all trajectories. “Succ. Steps” measures mean steps for successful trajectories only. Lower values indicate more efficient execution.
Figure 4: Ablation study on ALFWorld and Webshop benchmarks. Qwen2.5-1.5B-Instruct serves the base models.
Appendix figures & tables13 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Training curves on ALFWorld with Llama-3.2-3B-Instruct. Left: validation success rate. Right: Average episode length. Our method consistently achieves a higher success rate and shorter, more efficient trajectories than all baselines.
Figure 6: Training curves on Webshop with Llama-3.2-3B-Instruct. Left: validation success rate. Right: Average episode length. Our method consistently achieves a higher success rate and shorter, more efficient trajectories than all baselines.
Method
ALFWorld
WebShop
Pick
Look
Clean
Heat
Cool
Pick2
All
Score
Succ.
PPO
57.14
25.00
29.17
27.78
21.05
41.67
37.50
86.25
62.50
GRPO
57.14
25.00
20.83
33.33
21.05
41.67
36.72
82.66
65.63
RLOO
94.29
62.50
95.83
66.67
52.63
87.50
81.25
79.81
66.41
GIGPO
65.71
37.50
66.67
77.78
52.63
58.33
62.50
83.04
63.28
Ours
97.14
62.50
100.00
88.89
89.47
91.67
92.19
88.13
76.56
Appendix
Table 3: Performance comparison on ALFWorld and WebShop with Llama-3.2-3B-Instruct, the best result in each column is highlighted in bold.
Figure 7: Training accuracy of our discriminator on ALFWorld (top) and WebShop (bottom), reporting overall, success, and failure accuracy across training iterations.
Figure 8: Per-step time overhead of each training stage on ALFWorld (left) and WebShop (right).
Method
IID
OOD
GRPO
92.19
86.72
GiGPO
92.97
87.50
Ours
95.31
89.06
Appendix
Table 4: Final success rate (%) on ScienceWorld with Qwen2.5-7B-Instruct after 150 iterations. IID: seen task variants; OOD: unseen variants within seen categories.
Figure 9: Mean KL divergence (left) and clip fraction (right) during training on ALFWorld and WebShop, indicating stable policy updates.
Figure 10: Mean KL divergence (left) and clip fraction (right) during the trajectory evolution stage on ALFWorld and WebShop.
Step
Action
Observation
Credit
Dep(t)
0
go to drawer 1
The drawer 1 is closed.
Redundant
{1}
1
open drawer 1
The drawer 1 is open. In it, you see nothing.
Redundant
∅
2
go to drawer 2
The drawer 2 is closed.
Redundant
{3}
3
open drawer 2
The drawer 2 is open. In it, you see a spoon 1.
Redundant
∅
4
go to countertop 1
On the countertop 1, you see …a knife 1 …(and 18 other objects).
Necessary
{5,7,9}
5
take knife 1 from countertop 1
You pick up the knife 1 from the countertop 1.
Necessary
{7,9}
Appendix
Table 5: Case study of counterfactual credit analysis on a successful ALFWorld trajectory. The agent is asked to put a clean knife in sidetable . Each step t is removed from the trajectory (together with steps already identified as redundant) and the remaining actions are replayed in the environment: t is labeled Necessary if the task then fails, and Redundant otherwise. Dep(t) is the set of later steps whose actions become inexecutable ( “Nothing happens.” ) in this replay. When t is redundant, all steps in Dep(t) are marked redundant as well without further replay ( † ). Steps 0–3 are unsuccessful drawer searches and are all redundant; steps 4–9 form the necessary chain ( locate → grasp → clean → deliver ). These labels supervise the training of our step discriminator.
Figure 11: The prompt template of ALFWorld agents.
Figure 12: The prompt template of WebShop agents.
Figure 13: The think-only prompt template used during the trajectory evolution phase in ALFWorld. The predetermined action is provided and the model is asked to generate only the reasoning.
Figure 14: The think-only prompt template used during the trajectory evolution phase in WebShop. The predetermined action is provided and the model is asked to generate only the reasoning.
State Key Laboratory of Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China · FiT, Tencent, Shenzhen, China +2