RewardFlow: Topology-Aware Reward Propagation on State Graphs for Agentic RL with Large Language Models

Xiao Feng; Bo Han; Zhanke Zhou; Jiaqi Fan; Jiangchao Yao; Ka Ho Li; Dahai Yu; Michael Kwok-Po Ng

cs.AIMar 19, 2026

RewardFlow: Topology-Aware Reward Propagation on State Graphs for Agentic RL with Large Language Models

Authors: Xiao Feng, Bo Han, Zhanke Zhou, Jiaqi Fan, Jiangchao Yao, Ka Ho Li, Dahai Yu, Michael Kwok-Po Ng

Organizations: TMLR Group, Hong Kong Baptist University · TCL Corporate Research (HK) Co., Ltd · Cooperative Medianet Innovation Center, Shanghai Jiao Tong University · Department of Mathematics, Hong Kong Baptist University

Abstract

Reinforcement learning (RL) shows promise for enhancing LLM agentic reasoning, yet sparse terminal rewards hinder fine-grained optimization. Process reward modeling offers an alternative but incurs high computational costs, reward hacking risks, and annotation bottlenecks. We introduce RewardFlow, a lightweight method for estimating state-level rewards in agentic reasoning. By constructing state graphs that capture the intrinsic topological structure of trajectories, RewardFlow performs topology-aware propagation to estimate each state's contribution to success, yielding principled, annotation-free dense rewards. Used for RL optimization, RewardFlow substantially outperforms prior baselines across four agentic benchmarks: +6.2% average success rate on text-based tasks, +29.7% on visual reasoning over the strongest baseline across three model scales, and +10% accuracy on DeepResearch, with superior robustness and training efficiency. The implementation of RewardFlow is publicly available at https://github.com/tmlr-group/RewardFlow.

Figures & tables

Figure 1: Trajectories are merged into state nodes with directed action edges. Colors show distance to success (darker = closer); grey means unreachable. The graph reveals task topology and supports reliable process reward modeling.

Figure 2: Overview of RewardFlow . Each rectangular node represents a state; color indicates reward level. Given sampled agentic trajectories (sequences of states and actions), RewardFlow estimates action-wise rewards via three steps: (1) Graph Construction: Build state graph by aggregating equivalent states. (2) Graph Propagation: Backpropagate rewards from success nodes. (3) Action-level Reward Shaping: Map propagated state rewards back to trajectories and compute action rewards as the reward difference (gain) between post-action and pre-action states.

Figure 3: Comparison of total vs. unique states and actions across sampled trajectories of agentic reasoning using Qwen2.5-(VL)-3B-Instruct on ALFWorld, WebShop, Sokoban, and DeepResearch. Unique states and actions are substantially fewer than their total counts, highlighting significant state and repetition.

Type

Method

ALFWorld

WebShop

Sokoban

Pick

Look

Clean

Heat

Cool

Pick2

All

Score

Succ.

Score

Succ.

Qwen2.5-1.5B-Instruct

Prompting

Base

9.3 ±0.2

0.0 ±0.0

10.5 ±0.0

3.9 ±0.0

20.8 ±1.5

4.9 ±2.0

–

RL Training

RLOO

73.3 ±5.9

16.7 ±0.0

46.8 ±4.0

74.6 ±6.9

54.2 ±4.2

52.6 ±9.1

56.0 ±2.5

80.8 ±1.2

56.5 ±7.4

–

RL Training

GRPO

72.2 ±3.2

13.9 ±4.8

34.2 ±10.4

42.1 ±8.4

58.3 ±7.2

49.1 ±12.2

49.5 ±3.0

64.8 ±2.0

45.1 ±0.5

–

RL Training

GiGPO

65.9 ±5.7

26.7 ±17.3

54.7 ±8.2

33.8 ±9.1

50.6 ±6.2

48.6 ±10.3

50.8 ±2.8

81.7 ±5.5

60.7 ±4.8

–

Table 1: Main results (mean

\pm

std over three seeds). We report success rates (%) for ALFWorld (per-subtask and overall average), and both normalized score and success rate for WebShop and Sokoban. Bold and underline denote the best and second-best results per column.

Type	Method	Single-hop QA			Multi-hop QA				Avg.
Type	Method	NQ †	TriviaQA*	PopQA*	HotpotQA †	2Wiki*	Musique*	Bamboogle*	Avg.
Qwen2.5-3B-Instruct
RL Training	R1-Instruct	27.0	53.7	19.9	23.7	29.2	7.2	29.3	27.1
RL Training	Search-R1	34.1	54.5	37.8	32.4	31.9	10.3	26.4	32.5
RL Training	ZeroSearch	41.4	57.4	44.8	27.4	30.0	9.8	11.1	31.7
RL Training	StepSearch	–	–	–	34.5	32.0	17.4	34.4	–

Table 2: Performance comparison of RewardFlow on DeepResearch (trained on NQ + HotpotQA following GiGPO ( Feng et al., 2025b ) ). Reported as average accuracy (%). †in-distribution, * out-of-distribution.

Table 3: Out-of-distribution evaluation on ALFWorld. The agent solves household tasks with familiar objects in entirely novel environments (different rooms, layouts, furniture). We report the average success(%); higher is better.

Appendix figures & tables26 assets

Supplementary material from the paper’s appendix.

Appendix

	PBRS	Reward Machines	Furelos-Blanco	RewardFlow
State representation	Hand-crafted $\Phi$	Symbolic states	Prop. symbols	Raw text/visual obs
Structure source	Expert knowledge	Human FSA	Learned FSA	On-policy rollouts
Task-semantic knowledge	Yes	Yes	Yes	None
$\sim$ 100K token action space	✗	✗	✗	✓
Rebuilt per batch	N/A	✗	✗	✓

Appendix

Table 4: Comparison of RewardFlow with prior reward-shaping paradigms. “

\sim

100K token action space” indicates whether the method scales to LLM-agent action spaces; “Rebuilt per batch” indicates whether the shaping structure is reconstructed from current on-policy rollouts at every training step.

Training Step	Entropy	Invalid State Rate (%)	Invalid Action Rate (%)	Avg. Node	Avg. Edge	Success Rate (%)
0	1.099	33.1	41.0	24.1	46.9	4.1
50	0.555	0.3	0	33.1	55.9	44.5
100	0.295	0.1	0	19.9	30.6	62.8

Appendix

Table 5: Training progress of Qwen-2.5-1.5B-Instruct on the target task. Entropy, invalid rates, graph size, and success rate across training steps.

$\alpha_{\text{action}}$	$\alpha_{\text{traj}}$	ALFWorld 3B (%)
0	1	59.4
1	0	7.0
1	0.5	68.8
0.5	1	67.2
1	1	75.5

Appendix

Table 6: Ablation on the action-level and trajectory-level advantage weights

(\alpha_{\text{action}},\alpha_{\text{traj}})

on ALFWorld using Qwen2.5-3B-Instruct. Success rate (%); higher is better. Default

(1,1)

achieves the strongest performance and requires no tuning.

Type	Hyperparameter	ALFWorld	Webshop	Sokoban	DeepResearch
Qwen2.5-(VL)-1.5B/3B-Instruct
Learning	Training batch size	16	16	16	256
Learning	Minibatch size for policy update	256	64	256	512
Learning	Max interactive steps	25	15	15	4
Learning	Max prompt length	2048	4096	1024	4096
Learning	Max response length	512	512	512	512

Appendix

Table 7: Details of training configuration of experiments.

Environment	Avg. Nodes	Avg. Edges	Max Nodes	Max Edges
ALFWorld	28.8	55.9	42	77
WebShop	36.8	48.2	54	65
Sokoban	14.0	21.0	27	39

Appendix

Table 8: Average and maximum size of induced state graphs from 8 on-policy rollouts (Qwen2.5-1.5B/VL-3B-Instruct). Even in the worst case, graphs remain extremely compact.

Method	Success @100 steps (%)	Success @200 steps (%)	$\Delta$ (200-100)
RLOO	16.7	41.4	+24.7
GRPO	22.9	39.1	+16.2
GiGPO	19.8	33.6	+13.8
RewardFlow (ours)	49.5	70.3	+20.8

Appendix

Table 9: Extended training to 200 steps on Sokoban (Qwen2.5-VL-3B-Instruct). All methods fully converge well before 200 steps, and RewardFlow’s advantage further widens after convergence.

Model	Environment	Propagation	Success Rate (%)
Qwen-2.5-1.5B-Instruct	ALFWorld	Mean Distance	62.5
Qwen-2.5-1.5B-Instruct	ALFWorld	Min Distance	62.8
Qwen-2.5-VL-3B-Instruct	Sokoban	Mean Distance	33.6
Qwen-2.5-VL-3B-Instruct	Sokoban	Min Distance	49.2

Appendix

Table 10: Ablation on propagation strategies.

Method	Success Rate (%)
Base	16.4
RewardFlow (w/o state normalization)	53.9
RewardFlow (w/o noisy transition pruning)	60.2
RewardFlow	75.5

Appendix

Table 11: Performance of RewardFlow with or without each normalization operation on ALFWorld using Qwen2.5-3B-Instruct. Success rate (%).

Method	Rollouts	Avg. Nodes	Avg. Edges	Success Rate (%)
GiGPO	4	-	-	28.9
	6	-	-	51.6
	8	-	-	53.1
RewardFlow	4	17.1	28.8	42.2
	6	22.9	41.3	53.1
	8	28.8	55.9	62.8

Appendix

Table 12: Ablation on number of rollouts per training step using Qwen2.5-1.5B-Instruct in ALFWorld. Success rate (%) reported; RewardFlow results include average graph statistics.

Environment	BFS	PPR
ALFWorld	62.8	52.3
Sokoban	49.5	35.2

Appendix

Table 13: Comparison of BFS and Personalized PageRank (PPR) propagation strategies on the state graph constructed by RewardFlow . ALFWorld uses Qwen2.5-1.5B-Instruct; Sokoban uses Qwen2.5-VL-3B-Instruct. Success rate (%); higher is better.

Method	ALFWorld 1.5B	ALFWorld 3B	Sokoban 3B	WebShop 1.5B
GiGPO	$74.2\pm 1.7$	$75.2\pm 1.6$	$78.4\pm 2.6$	$60.2\pm 2.2$
RewardFlow	$\mathbf{76.8\pm 1.0}$	$\mathbf{82.8\pm 0.7}$	$\mathbf{81.8\pm 2.3}$	$\mathbf{66.9\pm 1.5}$

Appendix

Table 14: Comparison of GiGPO and RewardFlow under GiGPO’s original training settings (150 steps for ALFWorld/WebShop, 200 steps for Sokoban, batch size 32 for Sokoban). Success rate (%, mean

\pm

std over 3 seeds); bold indicates the better method.

Figure 12: The constructed state graph of the trajectory sampled from ALFWorld with 1 sampling rollout. The deeper color indicates a higher assigned reward. The initial state is in Node 0, and the success terminal state is in Node $\bigstar$ . The corresponding text representation of nodes and edges can be found in Figs. 15 and 16 .

Figure 13: The constructed state graph of the trajectories sampled from ALFWorld with 2 sampling rollouts. The deeper color indicates a higher assigned reward. The initial state is in Node 0, and the success terminal state is in Node $\bigstar$ . The corresponding text representation of nodes and edges can be found in Figs. 15 and 16 .

Figure 14: The constructed state graph of the trajectories sampled from ALFWorld with 3 sampling rollouts. The deeper color indicates a higher assigned reward. The initial state is in Node 0, and the success terminal state is in Node $\bigstar$ . The corresponding text representation of nodes and edges can be found in Figs. 15 and 16 .

Panel of Figure 15 — Figure 15: The node list of cases in ALFWorld in Figs. 12 , 13 , and 14 .

Panel of Figure 16 — Figure 16: The edge list of cases in ALFWorld in Figs. 12 , 13 , and 14 .

Figure 17: The constructed state graph of the trajectory sampled from WebShop with 1 sampling rollout. The deeper color indicates a higher assigned reward. The initial state is in Node 0, and the success terminal state is in Node $\bigstar$ . The corresponding text representation of nodes and edges can be found in Figs. 20 and 21 .

Figure 18: The constructed state graph of the trajectories sampled from WebShop with 2 sampling rollouts. The deeper color indicates a higher assigned reward. The initial state is in Node 0, and the success terminal state is in Node $\bigstar$ . The corresponding text representation of nodes and edges can be found in Figs. 20 and 21 .

Figure 19: The constructed state graph of the trajectory sampled from WebShop with 3 sampling rollouts. The deeper color indicates a higher assigned reward. The initial state is in Node 0, and the success terminal state is in Node $\bigstar$ . The corresponding text representation of nodes and edges can be found in Figs. 20 and 21 .

Panel of Figure 20 — Figure 20: The node list of cases in WebShop in Figs. 17 , 18 , and 19 .

Panel of Figure 21 — Figure 21: The edge list of cases in WebShop in Figs. 17 , 18 , and 19 .

Figure 22: The constructed state graph of the trajectory sampled from Sokoban with 1 sampling rollout. The deeper color indicates a higher assigned reward. The initial state is in Node 0, and the success terminal state is in Node $\bigstar$ . The corresponding text representation of nodes and edges can be found in Figs. 25 and 26 .

Figure 23: The constructed state graph of the trajectories sampled from Sokoban with 2 sampling rollout. The deeper color indicates a higher assigned reward. The initial state is in Node 0, and the success terminal state is in Node $\bigstar$ . The corresponding text representation of nodes and edges can be found in Figs. 25 and 26 .

Figure 24: The constructed state graph of the trajectories sampled from Sokoban with 3 sampling rollouts. The deeper color indicates a higher assigned reward. The initial state is in Node 0, and the success terminal state is in Node $\bigstar$ . The corresponding text representation of nodes and edges can be found in Figs. 25 and 26 .

Panel of Figure 25 — Figure 25: The node list of cases in Sokoban in Figs. 22 , 23 , and 24 .

Panel of Figure 26 — Figure 26: The edge list of cases in Sokoban in Figs. 22 , 23 , and 24 .

RL for LLM Agents

Reinforcement learning for large language model agents trains models to plan, use tools, and adapt through feedback from interactive tasks.

See all 608 papers

Dependency-Aware Reward Shaping for Agentic Reinforcement Learning
Oct 1, 2026Ziyi Chen, Yan Zhang, Jianhui Wei +2RL for Language Models Agentic RL
University of Illinois Urbana-Champaign · National University of Singapore · Zhejiang University +1
Lean4AgenticRL: Advancing Agentic RL with Verifiable Multi-level Process Rewards
Oct 15, 2026Ruida Wang, Gerald Friedland, Tong Zhang +1Agentic RL RL for Tool Use
Amazon Web Services · University of Illinois Urbana-Champaign
AstraFlow: Dataflow-Oriented Reinforcement Learning for Agentic LLMs
May 15, 2026Haizhong Zheng, Yizhuo Di, Jiahui Wang +7Agentic RL Reinforcement Learning
1Carnegie Mellon University · University of Michigan · 3UC Berkeley +1

Oct 1, 2026J/K move · Enter open · S save

Dependency-Aware Reward Shaping for Agentic Reinforcement Learning

Ziyi Chen, Yan Zhang, Jianhui Wei, Daoan Zhang+1

University of Illinois Urbana-Champaign · National University of Singapore · Zhejiang University+1

RL for Language Models Agentic RL Reward Shaping Credit Assignment in RL Step-Level Credit Assignment in RL Sparse-Reward RL+1

Open paper AskPDF arXiv

When training large language models with reinforcement learning, terminal rewards provide little guidance about which steps matter. Common methods for assigning step credit overlook that work built on uncorrected mistakes is wasted while independent work remains valid. With only a final success/failure reward, every step in a failed episode has zero total future reward, even when it made progress. We propose Dependency-Aware Reward Shaping (DARS), which represents task progress as predicates linked by prerequisite relations and assigns step-level credit over the dependency graph. An annotator marks which predicates each step verifies, invalidates, or repairs. Verified predicates are discounted according to graph distance from the nearest broken prerequisite, while independent predicates are unaffected. Repairs update these weights based on any errors that remain; invalidated predicates need re-verification to regain credit. A fixed potential converts these annotations into signed per-step rewards. A common reward and annotation interface allows DARS to integrate with a range of reasoning and agentic training methods, such as GiGPO and ARPO/AEPO, without changing their rollout strategies or optimizers. Across five task families and models from 1.5B to 8B, DARS improves success by up to 10 points over GiGPO trained with the same budget and harness (ALFWorld), raises the WebShop task score and Search-R1 QA accuracy, complements AEPO's entropy-based training on AIME24/25 with a Python interpreter, and exceeds OmniOPD in controlled tool-free reasoning comparisons at 1.7B and 4B. Ablations show that step-level credit, dependency attenuation, and graph topology each contribute. On ALFWorld, a distilled 8B annotator matches the API annotator, enabling DARS to run efficiently without a frontier judge. Code is available at https://github.com/JianhuiWei7/DARS.

Abstract

RL for LLM Agents

Explore similar work

Dependency-Aware Reward Shaping for Agentic Reinforcement Learning

Lean4AgenticRL: Advancing Agentic RL with Verifiable Multi-level Process Rewards

AstraFlow: Dataflow-Oriented Reinforcement Learning for Agentic LLMs